Revised: October 3, 2019

Published: December 17, 2019

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

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