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$.
Categories: cs.LO cs.CC