Rossman, Benjamin ;
Srinivasan, Srikanth
Separation of AC^0[oplus] Formulas and Circuits
Abstract
This paper gives the first separation between the power of formulas and circuits of equal depth in the AC^0[\oplus] basis (unbounded fanin AND, OR, NOT and MOD_2 gates). We show, for all d(n) <= O(log n/log log n), that there exist polynomialsize depthd circuits that are not equivalent to depthd formulas of size n^{o(d)} (moreover, this is optimal in that n^{o(d)} cannot be improved to n^{O(d)}). This result is obtained by a combination of new lower and upper bounds for Approximate Majorities, the class of Boolean functions {0,1}^n to {0,1} that agree with the Majority function on 3/4 fraction of inputs.
AC^0[\oplus] formula lower bound.
We show that every depthd AC^0[\oplus] formula of size s has a (1/8)error polynomial approximation over F_2 of degree O((log s)/d)^{d1}. This strengthens a classic $O(log s)^{d1}$ degree approximation for circuits due to Razborov. Since the Majority function has approximate degree Theta(\sqrt n), this result implies an \exp(\Omega(dn^{1/2(d1)})) lower bound on the depthd AC^0[\oplus] formula size of all Approximate Majority functions for all d(n) <= O(log n).
Monotone AC^0 circuit upper bound.
For all d(n) <= O(log n/log log n), we give a randomized construction of depthd monotone AC^0 circuits (without NOT or MOD_2 gates) of size \exp(O(n^{1/2(d1)}))} that compute an Approximate Majority function. This strengthens a construction of formulas of size \exp(O(dn^{1/2(d1)})) due to Amano.
BibTeX  Entry
@InProceedings{rossman_et_al:LIPIcs:2017:7390,
author = {Benjamin Rossman and Srikanth Srinivasan},
title = {{Separation of AC^0[oplus] Formulas and Circuits}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {50:150:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7390},
URN = {urn:nbn:de:0030drops73904},
doi = {10.4230/LIPIcs.ICALP.2017.50},
annote = {Keywords: circuit complexity, lower bounds, approximate majority, polynomial method}
}
07.07.2017
Keywords: 

circuit complexity, lower bounds, approximate majority, polynomial method 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 