2017/02/13 by Rossman, Benjamin, Srinivasan, Srikanth
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1702.03625
This paper gives the first separation between the power of \em formulas and \em circuits of equal depth in the AC0[⊕] basis (unbounded fan-in AND, OR, NOT and MOD2 gates). We show, for all d(n) ≤ O((log n)/(loglog n)), that there exist \em polynomial-size depth-d circuits that are not equivalent to \em depth-d formulas of size no(d) (moreover, this is optimal in that no(d) cannot be improved to nO(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 → \0,1\ that agree with the Majority function on 3/4 fraction of inputs. AC0[⊕] formula lower bound: We show that every depth-d AC0[⊕] formula of size s has a \em 1/8-error polynomial approximation over \mathbbF2 of degree O((1)/(d)log s)d-1. This strengthens a classic O(log s)d-1 degree approximation for \underlinecircuits due to Razborov. Since the Majority function has approximate 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(n) ≤ O(log n). Monotone AC0 circuit upper bound: For all d(n) ≤ 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 \underlineformulas of size exp(O(dn1/2(d-1))) due to Amano.