Symmetric Formulas for Products of Permutations

William He, Benjamin Rossman

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)$…