Theory of Computing
-------------------
Title : Separation of AC$^0[\oplus]$ Formulas and Circuits
Authors : Ben Rossman and Srikanth Srinivasan
Volume : 15
Number : 17
Pages : 1-20
URL : https://theoryofcomputing.org/articles/v015a017
Abstract
--------
We give the first separation between the power of formulas and
circuits in the $\AC^0[\oplus]$ basis (unbounded fan-in AND, OR, NOT
and MOD_2 gates). We show that there exist poly(n)-size depth-d
circuits that are not equivalent to any depth-d formula of size
$n^{o(d)}$ for all $d \le O({\log(n)}/{\log\log(n)})$. 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 a $3/4$ fraction
of the inputs.
_$\AC^0[\oplus]$ formula lower bound._ We show that every
depth-d $\AC^0[\oplus]$ formula of size s has a 1/4-error
polynomial approximation over $\F_2$ of degree $O((1/d)\log s)^{d-1}$.
This strengthens a classic $O(\log s)^{d-1}$ degree approximation for
circuits due to Razborov (1987). Since any polynomial that approximates
the Majority function has degree $\Omega(\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 \le O(\log n)$.
_Monotone $\AC^0$ circuit upper bound._ For all
$d \le 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 (2009).
--------------------------
A preliminary version of this paper appeared in the Proc. of the
44th International Colloquium on Automata, Languages, and Programming
(ICALP 2017).