Tree PCPs
summary
Introduces a new object called tree PCPs and constructs them for nondeterministic space-s computations, where each time step appends only poly(s, log t) bits per step and the verifier makes poly(s)·t^ε queries (ε>0). Construction uses locally testable tree codes built by tensoring block codes and algebraic codes (Reed–Solomon) plus a skewed local test; prover cost per step is n^ε and the scheme compiles in the random‑oracle model to a variant of incrementally verifiable computation, yielding the first such ROM construction.
AI-written summary · about
chapters (11)
- 0:00Tree PCPs introduction
- 1:57Probabilistically checkable proofs
- 4:07Incremental computation limits
- 9:30Circuit reachability and definition
- 15:40Main theorem and parameters
- 23:19Coding theory to PCP
- 32:19Tree codes from block codes
- 41:20Locally testable codes
- 51:15Tree PCP challenges
- 58:13Open questions and future
- 1:01:30Q&A
related talks
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
35mOblivious RAM for MPC
46mTree codes
01h 01mDerandomization: A Quick Tutorial
37mPPP-completeness with connections to Cryptography
26mPCPs and Instance Compression from a Cryptographic Lens
01h 01mMPC with Silent Preprocessing via Pseuodorandom Correlation Generators
30mProof Carrying Data