Revised: October 3, 2019
Published: December 17, 2019
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).
---------------------------
Licensed under a Creative Commons Attribution License (CC-BY)