License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.50
URN: urn:nbn:de:0030-drops-73904
Go to the corresponding LIPIcs Volume Portal

Rossman, Benjamin ; Srinivasan, Srikanth

Separation of AC^0[oplus] Formulas and Circuits

LIPIcs-ICALP-2017-50.pdf (0.5 MB)


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

  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 =		{},
  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
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI