![]() |
![]() |
We consider the action of a linear subspace U of {0,1}n on the set of AC0 formulas with inputs labeled by literals in the set {X1,¯X1,…,Xn,¯Xn}, where an element u∈U acts on formulas by transposing the ith pair of literals for all i∈[n] such that ui=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⋅2dn1/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 2d(n1/d−1) lower bound on the P-invariant depth d+1 formula size of PARITY. Quantitatively this improves the best known Ω(2184d(n1/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⊂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 2d(m1/d−1) where m is the minimum Hamming weight of a vector in U⊥∖V⊥.