Technical Report MSC-2021-16

TR#:MSC-2021-16
Class:MSC
Title: Small Circuits Imply Efficient Arthur-Merlin Protocols
Authors: Michael Ezra
Supervisors: Ron Rothblum
PDFCurrently accessibly only within the Technion network
Abstract: 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 give evidence for a possible negative answer for a minimalistic version of the above question. Namely, showing that the inner product function cannot be \emph{approximated} by a small DNF augmented with a single layer of parity gates. To do so, we show that the existence of such a small circuit would have unexpected implications for interactive variants of the Data Streaming and Communication Complexity models, in particular:

\begin{enumerate} \item An $O(d)$-message protocol in the Arthur-Merlin Data Streaming model for every degree $d$ polynomial (over $GF(2)$). In particular, this gives an AM protocol for a variant of the well-studied triangle counting problem. \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. \end{enumerate}

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2021/MSC/MSC-2021-16), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2021
To the main CS technical reports page

Computer science department, Technion
admin