Symmetric Formulas for Products of Permutations
share
We study the formula complexity of the word problem 𝖶𝗈𝗋𝖽_S_n,k : {0,1}^kn^2→{0,1}: given n-by-n permutation matrices M_1,…,M_k, compute the (1,1)-entry of the matrix product M_1⋯ M_k. An important feature of this function is that it is invariant under action of S_n^k-1 given by (π_1,…,π_k-1)(M_1,…,M_k) = (M_1π_1^-1,π_1M_2π_2^-1,…,π_k-2M_k-1π_k-1^-1,π_k-1M_k). This symmetry is also exhibited in the smallest known unbounded fan-in {𝖠𝖭𝖣,𝖮𝖱,𝖭𝖮𝖳}-formulas for 𝖶𝗈𝗋𝖽_S_n,k, which have size n^O(log k). In this paper we prove a matching n^Ω(log k) lower bound for S_n^k-1-invariant formulas computing 𝖶𝗈𝗋𝖽_S_n,k. This result is motivated by the fact that a similar lower bound for unrestricted (non-invariant) formulas would separate complexity classes 𝖭𝖢^1 and 𝖫𝗈𝗀𝗌𝗉𝖺𝖼𝖾. 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 {𝖬𝖠𝖩,𝖠𝖭𝖣,𝖮𝖱,𝖭𝖮𝖳}-formula size of 𝖶𝗈𝗋𝖽_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 {𝖠𝖭𝖣,𝖮𝖱,𝖭𝖮𝖳}-formula size in the case where G is an abelian group.
READ FULL TEXT
