2026-07-23T05:28:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7423 2024-03-06T10:40:28Z ddc:004 open_access

Subspace-Invariant AC^0 Formulas Rossman, Benjamin lower bounds size-depth tradeoff parity symmetry in computation The n-variable PARITY function is computable (by a well-known recursive construction) by AC^0 formulas of depth d+1 and leaf size n2^{dn^{1/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 2^{d(n^{1/d}-1)} lower bound on the size of syntactically P-invariant depth d+1 formulas for PARITY. Quantitatively, this beats the best 2^{Omega(d(n^{1/d}-1))} lower bound in the non-invariant setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Rossman 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.93 urn:nbn:de:0030-drops-74235 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.93 eng https://creativecommons.org/licenses/by/3.0/legalcode