Abstract
We study the formula complexity of the word problem Word_{S_n,k} : {0,1}^{kn²} → {0,1}: given nbyn permutation matrices M₁,… ,M_k, compute the (1,1)entry of the matrix product M₁⋯ M_k. An important feature of this function is that it is invariant under action of S_n^{k1} given by (π₁,… ,π_{k1})(M₁,… ,M_k) = (M₁π₁^{1},π₁M₂π₂^{1},… ,π_{k2}M_{k1}π_{k1}^{1},π_{k1}M_k).
This symmetry is also exhibited in the smallest known unbounded fanin {and,or,not}formulas for Word_{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^{k1}invariant formulas computing Word_{S_n,k}. This result is motivated by the fact that a similar lower bound for unrestricted (noninvariant) formulas would separate complexity classes NC¹ and Logspace.
Our more general main theorem gives a nearly tight n^d(k^{1/d}1) lower bound on the G^{k1}invariant depthd {maj,and,or,not}formula size of 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^{k1}invariant depthd {and,or,not}formula size in the case where G is an abelian group.
BibTeX  Entry
@InProceedings{he_et_al:LIPIcs.ITCS.2023.68,
author = {He, William and Rossman, Benjamin},
title = {{Symmetric Formulas for Products of Permutations}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {68:168:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17571},
URN = {urn:nbn:de:0030drops175717},
doi = {10.4230/LIPIcs.ITCS.2023.68},
annote = {Keywords: circuit complexity, groupinvariant formulas}
}
Keywords: 

circuit complexity, groupinvariant formulas 
Collection: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) 
Issue Date: 

2023 
Date of publication: 

01.02.2023 