Symmetric Formulas for Products of Permutations

Abstract

We study the formula complexity of the word problem ${\mathsf{Word}}_{S_n,k}:\{0,1{\}}^{k{n}^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 \[ (π_1,\dots,π_{k-1})(M_1,\dots,M_k) = (M_1π_1^{-1},π_1M_2π_2^{-1},\dots,π_{k-2}M_{k-1}π_{k-1}^{-1},π_{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.

ITCS 2023