 When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.50
URN: urn:nbn:de:0030-drops-73904
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7390/
 Go to the corresponding LIPIcs Volume Portal

Separation of AC^0[oplus] Formulas and Circuits

 pdf-format:

Abstract

This paper gives the first separation between the power of formulas and circuits of equal depth in the AC^0[\oplus] basis (unbounded fan-in AND, OR, NOT and MOD_2 gates). We show, for all d(n) <= O(log n/log log n), that there exist polynomial-size depth-d circuits that are not equivalent to depth-d 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 depth-d AC^0[\oplus] formula of size s has a (1/8)-error polynomial approximation over F_2 of degree O((log s)/d)^{d-1}. This strengthens a classic $O(log s)^{d-1}$ 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(d-1)})) lower bound on the depth-d 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 depth-d monotone AC^0 circuits (without NOT or MOD_2 gates) of size \exp(O(n^{1/2(d-1)}))} that compute an Approximate Majority function. This strengthens a construction of formulas of size \exp(O(dn^{1/2(d-1)})) 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:1--50:13},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-041-5},
ISSN =	{1868-8969},
year =	{2017},
volume =	{80},
editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7390},
URN =		{urn:nbn:de:0030-drops-73904},
doi =		{10.4230/LIPIcs.ICALP.2017.50},
annote =	{Keywords: circuit complexity, lower bounds, approximate majority, polynomial method}
}

 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: 06.07.2017

DROPS-Home | Imprint | Privacy 