Symmetric Formulas for Products of Permutations
We study the formula complexity of the word problem WordSn,k : (0, 1)kn2 → (0, 1): given n-by-n permutation matrices M1,..., Mk, compute the (1, 1)-entry of the matrix product M1 · · · Mk. An important feature of this function is that it is invariant under action of Snk−1 given by (π1,..., πk−1)(M1,..., Mk) = (M1π1−1, π1M2π2−1,..., πk−2Mk−1πk−−11, πk−1Mk). This symmetry is also exhibited in the smallest known unbounded fan-in (and, or, not)-formulas for WordSn,k, which have size nO(log k). In this paper we prove a matching nΩ(log k) lower bound for Snk−1-invariant formulas computing WordSn,k. This result is motivated by the fact that a similar lower bound for unrestricted (non-invariant) formulas would separate complexity classes NC1 and Logspace. Our more general main theorem gives a nearly tight nd(k1/d−1) lower bound on the Gk−1invariant depth-d (maj, and, or, not)-formula size of WordG,k for any finite simple group G whose minimum permutation representation has degree n. We also give nearly tight lower bounds on the Gk−1-invariant depth-d (and, or, not)-formula size in the case where G is an abelian group.
