Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-127 | 30th August 2021 21:44

Small Circuits Imply Efficient Arthur-Merlin Protocols



The inner product function $\langle x,y \rangle = \sum_i x_i y_i \bmod 2$ can be easily computed by a (linear-size) ${AC}^0(\oplus)$ circuit: that is, a constant depth circuit with AND, OR and parity (XOR) gates. But what if we impose the restriction that the parity gates can only be on the bottom most layer (closest to the input)? Namely, can the inner product function be computed by an ${AC}^0$ circuit composed with a single layer of parity gates? This seemingly simple question is an important open question at the frontier of circuit lower bound research.

In this work, we focus on a minimalistic version of the above question. Namely, whether the inner product function cannot be \emph{approximated} by a small $DNF$ augmented with a single layer of parity gates. Our main result shows that the existence of such a circuit would have unexpected implications for interactive proofs, or more specifically, for interactive variants of the Data Streaming and Communication Complexity models. In particular, we show that the existence of such a small (i.e., polynomial-size) circuit yields:

\item An $O(d)$-message protocol in the Arthur-Merlin Data Streaming model for every $n$-variate, degree $d$ polynomial (over $\mathbb{GF}(2)$), using only $\widetilde{O}\left(d\right)\cdot\log(n)$ communication and space complexity. In particular, this gives an AM$[2]$ Data Streaming protocol for a variant of the well-studied triangle counting problem, with poly-logarithmic communication and space complexities.

\item A $2$-message communication complexity protocol for any sparse (or low degree) polynomial, and for any function computable by an ${AC}^0(\oplus)$ circuit. Specifically, for the latter, we obtain a protocol with communication complexity that is poly-logarithmic in the size of the ${AC}^0(\oplus)$ circuit.

ISSN 1433-8092 | Imprint