Separation of AC0 [⊕] formulas and circuits
Published
Conference Paper
© Benjamin Rossman and Srikanth Srinivasan;. This paper gives the first separation between the power of formulas and 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/log log n ), that there exist polynomial-size depth-d circuits that are not equivalent to 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 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 1/8-error polynomial approximation over F2 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 [12]. 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/log log 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(dn 1/2(d-1) )) due to Amano [1].
Full Text
Duke Authors
Cited Authors
- Rossman, B; Srinivasan, S
Published Date
- July 1, 2017
Published In
Volume / Issue
- 80 /
International Standard Serial Number (ISSN)
- 1868-8969
International Standard Book Number 13 (ISBN-13)
- 9783959770415
Digital Object Identifier (DOI)
- 10.4230/LIPIcs.ICALP.2017.50
Citation Source
- Scopus