Separation of AC${}^0[\oplus ]$ Formulas and Circuits

Abstract

This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the ${\mathrm{AC}}^0[\oplus ]$ basis (unbounded fan-in AND, OR, NOT and MOD${}_2$ gates). We show, for all $d(n)\le O(\frac{\log n}{\log \log n})$, that there exist {\em polynomial-size depth-$d$ circuits} that are not equivalent to {\em 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 {\em 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. ${\mathrm{AC}}^0[\oplus ]$ formula lower bound: We show that every depth-$d$ ${\mathrm{AC}}^0[\oplus ]$ formula of size $s$ has a {\em $1/8$-error polynomial approximation} over ${\mathbb{F}}_2$ of degree $O(\frac{1}{d}\log s{)}^{d-1}$. This strengthens a classic $O(\log s{)}^{d-1}$ degree approximation for \underline{circuits} due to Razborov. Since the Majority function has approximate degree $\Theta (\sqrt{n})$, this result implies an $\exp (\Omega (d{n}^{1/2(d-1)}))$ lower bound on the depth-$d$ ${\mathrm{AC}}^0[\oplus ]$ formula size of all Approximate Majority functions for all $d(n)\le O(\log n)$. Monotone ${\mathrm{AC}}^0$ circuit upper bound: For all $d(n)\le O(\frac{\log n}{\log \log n})$, we give a randomized construction of depth-$d$ monotone ${\mathrm{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 \underline{formulas} of size $\exp (O(d{n}^{1/2(d-1)}))$ due to Amano.