We study the formula complexity of the word problem $\mathsf{ Word}_{ S_n,k} : \{ 0,1\}^{ kn^2} \to \{ 0,1\}$: given $n$-by-$n$ permutation matrices $M_1,\dots,M_k$, compute the $(1,1)$-entry of the matrix product $M_1\cdots M_k$. An important feature of this function is that it is invariant under action of $S_n^{ k-1}$ given by \[ (\pi_1,\dots,\pi_{ k-1})(M_1,\dots,M_k) = (M_1\pi_1^{ -1},\pi_1M_2\pi_2^{ -1},\dots,\pi_{ k-2}M_{ k-1}\pi_{ k-1}^{ -1},\pi_{ k-1}M_k). \] This symmetry is also exhibited in the smallest known unbounded fan-in $\{ \mathsf{ AND},\mathsf{ OR},\mathsf{ NOT}\}$-formulas for $\mathsf{ Word}_{ S_n,k}$, which have size $n^{ O(\log k)}$. In this paper we prove a matching $n^{ \Omega(\log k)}$ lower bound for $S_n^{ k-1}$-invariant formulas computing $\mathsf{ Word}_{ S_n,k}$. This result is motivated by the fact that a similar lower bound for unrestricted (non-invariant) formulas would separate complexity classes $\mathsf{ NC}^1$ and $\mathsf{ Logspace}$. Our more general main theorem gives a nearly tight $n^{ d(k^{ 1/d}-1)}$ lower bound on the $G^{ k-1}$-invariant depth-$d$ $\{ \mathsf{ MAJ},\mathsf{ AND},\mathsf{ OR},\mathsf{ NOT}\}$-formula size of $\mathsf{ Word}_{ G,k}$ for any finite simple group $G$ whose minimum permutation representation has degree~$n$. We also give nearly tight lower bounds on the $G^{ k-1}$-invariant depth-$d$ $\{ \mathsf{ AND},\mathsf{ OR},\mathsf{ NOT}\}$-formula size in the case where $G$ is an abelian group.
Categories: cs.CC
