2022/11/28 by He, William, Rossman, Benjamin
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2211.15520
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-1-1,π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 n^d(k1/d-1) lower bound on the Gk-1-invariant 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.