Separation of AC⁰[⊕] formulas and circuits

We give the first separation between the power of formulas and circuits in the AC0[⊕] basis (unbounded fan-in AND, OR, NOT and MOD2 gates). We show that there exist poly(n)-size depth-d circuits that are not equivalent to any depth-d formula of size no(d) for all d ≤ O(log(n)/loglog(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 → {0,1} that agree with the Majority function on a 3/4 fraction of the inputs. AC0[⊕] formula lower bound. We show that every depth-d AC0[⊕] formula of size s has a 1/4-error polynomial approximation over F2 of degree O((1/d)logs)d−1. This strengthens a classic O(logs)d−1degree approximation for circuits due to Razborov (1987). Since any polynomial that approximates the Majority function has degree Ω(√n), this result implies an exp(Ω(dn1/2(d−1))) lower bound on the depth-d AC0[⊕] formula size of all Approximate Majority functions for all d ≤ O(logn). Monotone AC0 circuit upper bound. For all d ≤ O(log(n)/loglog(n)), we give a randomized construction of depth-d monotone AC0 circuits (without NOT or MOD2 gates) of size exp(O(n1/2(d−1))) that compute an Approximate Majority function. This strengthens a construction of formulas of size exp(O(dn1/2(d−1))) due to Amano (2009).

Duke Scholars

Author Benjamin Rossman Computer Science