Volume 15 (2019) Article 17 pp. 1-20
Separation of AC$^0[\oplus]$ Formulas and Circuits
Received: August 11, 2017
Revised: October 3, 2019
Published: December 17, 2019
Download article from ToC site:
[PDF (268K)]    [PS (1351K)]    [PS.GZ (317K)]
[Source ZIP]
Keywords: formulas, circuits, lower bounds, AC$^0$
ACM Classification: F.1.3, F.2.3
AMS Classification: 68Q17, 68Q15

Abstract: [Plain Text Version]


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).

---------------------------