Subspace-invariant AC0 formulas

Conference Paper

The n-variable PARITY function is computable (by a well-known recursive construction) by AC formulas of depth d + 1 and leafsize n·2 . 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(n -1) lower bound on the size of syntactically P-invariant depth d + 1 formulas for PARITY. Quantitatively, this beats the best 2 ) lower bound in the noninvariant setting [16]. 0 dn1/d 1/d ω(d(n1/d-1)

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