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:
\begin{enumerate}
\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.
\end{enumerate}
1. Added some relevant citations.
2. Correcting some spelling mistakes and typos.
3. Reprahsing a few sentences in the light of comments we received from the ICTS2022 reviewers after our paper has been accepted to that (upcoming) conference.
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:
\begin{enumerate}
\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.
\end{enumerate}
