Ezra, Michael ;
Rothblum, Ron D.
Small Circuits Imply Efficient ArthurMerlin Protocols
Abstract
The inner product function ⟨ x,y ⟩ = ∑_i x_i y_i mod 2 can be easily computed by a (linearsize) AC⁰(⊕) 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⁰ 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 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., polynomialsize) circuit yields:
1) An O(d)message protocol in the ArthurMerlin Data Streaming model for every nvariate, degree d polynomial (over GF(2)), using only Õ(d) ⋅log(n) communication and space complexity. In particular, this gives an AM[2] Data Streaming protocol for a variant of the wellstudied triangle counting problem, with polylogarithmic communication and space complexities.
2) A 2message communication complexity protocol for any sparse (or low degree) polynomial, and for any function computable by an AC⁰(⊕) circuit. Specifically, for the latter, we obtain a protocol with communication complexity that is polylogarithmic in the size of the AC⁰(⊕) circuit.
BibTeX  Entry
@InProceedings{ezra_et_al:LIPIcs.ITCS.2022.67,
author = {Ezra, Michael and Rothblum, Ron D.},
title = {{Small Circuits Imply Efficient ArthurMerlin Protocols}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {67:167:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15663},
URN = {urn:nbn:de:0030drops156635},
doi = {10.4230/LIPIcs.ITCS.2022.67},
annote = {Keywords: Circuits Complexity, Circuit Lower Bounds, Communication Complexity, Data Streaming, ArthurMerlin games, Interactive Proofs}
}
25.01.2022
Keywords: 

Circuits Complexity, Circuit Lower Bounds, Communication Complexity, Data Streaming, ArthurMerlin games, Interactive Proofs 
Seminar: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Issue date: 

2022 
Date of publication: 

25.01.2022 