Local Proofs Approaching the Witness Length
summary
Constructs constant-round IOPs for Circuit-SAT with communication arbitrarily close to the circuit size (rate → 1), constant query complexity and quasi-linear prover/verifier time, and extends to NP relations decidable in bounded polynomial space with total communication (1+ε)·|witness| under standard fine-grained assumptions. Key tools are arithmetization via multilinear extensions, high-rate tensor codes, and a novel sumcheck on tensor codes plus PCP-of-proximity composition to push queries to a constant; the protocols are explicit and achieve the stated parameters.
AI-written summary · about
chapters (8)
- 0:00Welcome and logistics
- 5:25Introduction to PCP theorem
- 9:35Open questions on PCP length
- 14:05Interactive oracle proofs
- 21:09Encoding methods for IOPs
- 27:55Arithmetization and sum-check
- 35:02Tensor codes and implementation
- 48:07Future research and conclusion
related talks
01h 09mProofs - Practice 1
43mConstant-Round Arguments from One-Way Functions
01h 13mA Zero-Knowledge PCP Theorem
01h 08mIncrementally Verifiable Computation for NP from Standard Assumptions
26mPCPs and Instance Compression from a Cryptographic Lens
01h 08mTutorial on Proof Systems
57mThe Cryptographic Lens: Visions of our Past and Future
01h 06mLattice-based Zero-knowledge Proofs