Izaak Meckler
Can we use the rep theory of $$S_n$$ to prove circuit lower bounds?

Let $$S_n$$ be the symmetric group on $$n$$ objects. $$S_n$$ has the following properties:

• Every faithful (i.e., injective) representation of $$S_n$$ has dimension $$n - 1$$.
• If we think of $$S_{2^k}$$ as the group of reversible circuits (with generators given by a universal set of gates), the word problem (suitably interpreted) of $$S_{2^k}$$ is $$\mathrm{coNP}$$ complete.

Taken together, these two facts give a sort of lower bound on a certain kind of read-once program for computing a $$\mathrm{coNP}$$ hard problem. Can read-many programs be somehow transformed into representations of the symmetric group in such a way that a small program yields a small dimensional representation? If so, the non-existence of small-dimensional representations would prove that no small program can exist for the word problem of $$S_{2^k}$$, thus proving a lower bound for $$\mathrm{coNP}$$.