Small Circuits Imply Efficient Arthur-Merlin Protocols

2021-08-30-DM-Small Circuits Imply Efficient Arthur-Merlin Protocols

paper

Result

Setup

Small Boolean Circuits

• $<x,y> = \sum_i x_i y_i \mod 2$ is the inner product function.
• It can be easily computed by constant depth circuits with $\oplus$ gates (AC$^0_\oplus$).
• What if we only allow $\oplus$ gates only at the bottom?
• If we do not allow $\oplus$ gates than showing a lower bound is easy.
• DNF of parities has also an exponential lower bound.
• Depth 3 circuits only have a weak quadratic lower bound.
• For arbitrary depth (AC$^0_\oplus$) and the number of parity gates is linear, a lower bound is known.

Communication Complexity

• Arthur-Merlin protocol where there is an all powerful prover and a verifier.
• AM Data Streaming Model (AM[$k$])
  • Merlin sees the complete input.
  • Verifier sees a stream and is space bounded.
  • Phases:
    • First phase: Verifier engages in a $k$-message public coin protocol with the prover, resulting in a transcript $\tau$.
    • Second phase: Verifier works deterministically on the input as a stream and is allowed to look at $\tau$.
    • Third phase: Verifier accepts or rejects.
  • There exists a strategy for Merlin that convinces the verifier to accept true statements.
  • No strategy makes the Verifier accept false statements.
• This also can work as a communication complexity protocol with the same bounds.

Result

• If there exists a DNF of parities of size $s$ that computes the inner product function on $5/6+\epsilon$ fraction of the inputs for some constant $\epsilon$. Then there exists a AM[$k$] with $\tilde O(d)\log s$ proof length, space complexity and randomness complexity for every polynomial over $GF(2)$.

Proof

Holographic IP

• Verifier instead of having the input is given an encoding of the input, similar to PCP.
• Construct a protocol that works for most inputs.
  • Prover picks sends an index to a satisfied clause. Verifier, verifies that this is correct.
    • The size bound is $\log s$.
  • However, large width DNF would be a problem.
  • We can see DNF clauses as a system of linear equations. We now remove wide clauses but make sure that the rank of this system does not decrease.
  • Notice that if the DNF is not fulfilled then there does not exist a single clause that is true. Hence the prover cannot prove this.
• To make this protocol work for all most inputs we want to use the equation $<x,y> = <x \oplus u,y\oplus v> \oplus <x\oplus u,v> \oplus <u,y\oplus v> \oplus <u,v>$.
  • However, for this would need to verify zero cases too.
  • A cheating prover cannot lie in the one cases but has to lie in the zero cases.
  • We expect roughly equal amount of ones and zero cases of our equation.
  • The Verifier will now ask for a couple of randomly chosen strings $u,v$, check the one claims and accepts the zero claims.
  • Then it checks that the average value is close enough to the expected value.