Subspace-invariant AC0 formulas
Publication
, Conference
Rossman, B
Published in: Leibniz International Proceedings in Informatics, LIPIcs
July 1, 2017
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].
Duke Scholars
Published In
Leibniz International Proceedings in Informatics, LIPIcs
DOI
ISSN
1868-8969
ISBN
9783959770415
Publication Date
July 1, 2017
Volume
80
Citation
APA
Chicago
ICMJE
MLA
NLM
Rossman, B. (2017). Subspace-invariant AC0 formulas. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 80). https://doi.org/10.4230/LIPIcs.ICALP.2017.93
Rossman, B. “Subspace-invariant AC0 formulas.” In Leibniz International Proceedings in Informatics, LIPIcs, Vol. 80, 2017. https://doi.org/10.4230/LIPIcs.ICALP.2017.93.
Rossman B. Subspace-invariant AC0 formulas. In: Leibniz International Proceedings in Informatics, LIPIcs. 2017.
Rossman, B. “Subspace-invariant AC0 formulas.” Leibniz International Proceedings in Informatics, LIPIcs, vol. 80, 2017. Scopus, doi:10.4230/LIPIcs.ICALP.2017.93.
Rossman B. Subspace-invariant AC0 formulas. Leibniz International Proceedings in Informatics, LIPIcs. 2017.
Published In
Leibniz International Proceedings in Informatics, LIPIcs
DOI
ISSN
1868-8969
ISBN
9783959770415
Publication Date
July 1, 2017
Volume
80