Math @ Duke

Publications [#348675] of Benjamin Rossman
Papers Published
 Rossman, B; Srinivasan, S, Separation of AC^{0}[⊕] formulas and circuits,
Leibniz International Proceedings in Informatics, Lipics, vol. 80
(July, 2017), ISBN 9783959770415 [doi]
(last updated on 2022/05/19)
Abstract: This paper gives the first separation between the power of formulas and circuits of equal depth in the AC0[⊕] basis (unbounded fanin AND, OR, NOT and MOD2 gates). We show, for all d(n) ≤ O( log n/log log n ), that there exist polynomialsize depthd circuits that are not equivalent to depthd 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 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 depthd AC0[⊕] formula of size s has a 1/8error polynomial approximation over F2 of degree O( 1/d log s)d1. This strengthens a classic O(log s)d1 degree approximation for circuits due to Razborov [12]. Since the Majority function has approximate degree ⊖(√ n), this result implies an exp(ω(dn1/2(d1))) lower bound on the depthd 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/log log n ), we give a randomized construction of depthd monotone AC0 circuits (without NOT or MOD2 gates) of size exp(O(n1/2(d1))) that compute an Approximate Majority function. This strengthens a construction of formulas of size exp(O(dn 1/2(d1) )) due to Amano [1].


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

