Math @ Duke

Publications [#348667] of Benjamin Rossman
Papers Published
 Rossman, B; Srinivasan, S, Separation of AC^{0}[⊕] formulas and circuits,
Theory of Computing, vol. 15
(January, 2019) [doi]
(last updated on 2022/05/19)
Abstract: We give the first separation between the power of formulas and circuits in the AC0[⊕] basis (unbounded fanin AND, OR, NOT and MOD2 gates). We show that there exist poly(n)size depthd circuits that are not equivalent to any depthd 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 depthd AC0[⊕] formula of size s has a 1/4error 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 depthd 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 depthd 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).


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

