Small Circuits Imply Efficient Arthur-Merlin Protocols

on YouTube ↗34m

" summary

Assumes a polynomial-size DNF of parities that computes the inner product on > 5/6 accuracy and derives extremely efficient public-coin (AM/R2) protocols: quasi-linear proof length and logarithmic space for constant-degree polynomials in the streaming model, a one-round protocol with communication O(D log n) for degree-D polynomials, and a polylogarithmic one-round protocol for AC0 languages. Construction passes through a one-round holographic interactive proof querying the parity-layer encoding and uses self-correction plus error amplification.

AI-written summary · about

" chapters (9)

1. 0:00Introduction and abstract
2. 0:36Core definitions and concepts
3. 4:02Motivation for approximation
4. 5:43Boolean circuit background
5. 10:15Data streaming and IP models
6. 14:02Streaming model results
7. 17:07Communication complexity
8. 19:40Technical construction
9. 31:21Open problems and conclusion