{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:41:12Z","timestamp":1753890072316,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2019,7,24]],"date-time":"2019-07-24T00:00:00Z","timestamp":1563926400000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,7,24]],"date-time":"2019-07-24T00:00:00Z","timestamp":1563926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,7,24]],"date-time":"2019-07-24T00:00:00Z","timestamp":1563926400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>We consider the action of a linear subspace $U$ of $\\{0,1\\}^n$ on the set of AC$^0$ formulas with inputs labeled by literals in the set $\\{X_1,\\overline X_1,\\dots,X_n,\\overline X_n\\}$, where an element $u \\in U$ acts on formulas by transposing the $i$th pair of literals for all $i \\in [n]$ such that $u_i=1$. A formula is {\\em $U$-invariant} if it is fixed by this action. For example, there is a well-known recursive construction of depth $d+1$ formulas of size $O(n{\\cdot}2^{dn^{1\/d}})$ computing the $n$-variable PARITY function; these formulas are easily seen to be $P$-invariant where $P$ is the subspace of even-weight elements of $\\{0,1\\}^n$. In this paper we establish a nearly matching $2^{d(n^{1\/d}-1)}$ lower bound on the $P$-invariant depth $d+1$ formula size of PARITY. Quantitatively this improves the best known $\\Omega(2^{\\frac{1}{84}d(n^{1\/d}-1)})$ lower bound for {\\em unrestricted} depth $d+1$ formulas, while avoiding the use of the switching lemma. More generally, for any linear subspaces $U \\subset V$, we show that if a Boolean function is $U$-invariant and non-constant over $V$, then its $U$-invariant depth $d+1$ formula size is at least $2^{d(m^{1\/d}-1)}$ where $m$ is the minimum Hamming weight of a vector in $U^\\bot \\setminus V^\\bot$.<\/jats:p>","DOI":"10.23638\/lmcs-15(3:3)2019","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T17:37:53Z","timestamp":1743701873000},"source":"Crossref","is-referenced-by-count":0,"title":["Subspace-Invariant AC$^0$ Formulas"],"prefix":"10.23638","volume":"Volume 15, Issue 3","author":[{"given":"Benjamin","family":"Rossman","sequence":"first","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2019,7,24]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/1806.04831v4","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/1806.04831v4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T17:37:54Z","timestamp":1743701874000},"score":1,"resource":{"primary":{"URL":"http:\/\/lmcs.episciences.org\/4588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,24]]},"references-count":0,"URL":"https:\/\/doi.org\/10.23638\/lmcs-15(3:3)2019","relation":{"has-preprint":[{"id-type":"arxiv","id":"1806.04831v2","asserted-by":"subject"},{"id-type":"arxiv","id":"1806.04831v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1806.04831","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1806.04831","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2019,7,24]]},"article-number":"4588"}}