Volume 15 (2019) Article 17 pp. 1-20

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

by Ben Rossman and Srikanth Srinivasan

Received: August 11, 2017
Revised: October 3, 2019
Published: December 17, 2019

$\newcommand{\cclass}[1]{{\textsf{#1}}} \newcommand{\poly}{\mathop{\mathrm{poly}}} \newcommand{\F}{\mathbb{F}} \newcommand{\AC}{\cclass{AC}}$

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

DOI: 10.4086/toc.2019.v015a017

© 2019 Ben Rossman and Srikanth Srinivasan
Licensed under a Creative Commons Attribution License (CC-BY)