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