Subspace-invariant AC0 formulas
Published
Conference Paper
© Benjamin Rossman;. The n-variable PARITY function is computable (by a well-known recursive construction) by AC0 formulas of depth d + 1 and leafsize n·2dn1/d. These formulas are seen to possess a certain symmetry: they are syntactically invariant under the subspace P of even-weight elements in {0, 1}n, which acts (as a group) on formulas by toggling negations on input literals. In this paper, we prove a 2d(n1/d-1) lower bound on the size of syntactically P-invariant depth d + 1 formulas for PARITY. Quantitatively, this beats the best 2ω(d(n1/d-1)) lower bound in the noninvariant setting [16].
Full Text
Duke Authors
Cited Authors
- Rossman, B
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.93
Citation Source
- Scopus