46
$\begingroup$

Inspired by this question and in particular the final paragraph of Or's answer, I have the following question:

Do you know of any applications of the representation theory of the symmetric group in TCS?

The symmetric group $S_n$ is the group of all permutations of $\{1, \ldots, n\}$ with group operation composition. A representation of $S_n$ is a homomorphism from $S_n$ to the general linear group of invertible $n \times n$ complex matrices. A representation acts on $\mathbb{C}^n$ by matrix multiplication. An irreducible representation of $S_n$ is an action that leaves no proper subspace of $\mathbb{C}^n$ invariant. Irreducible representations of finite groups allow one to define a Fourier transform over non-abelian groups. This Fourier transform shares some of the nice properties of the discrete Fourier transform over cyclic/abelian groups. For example convolution becomes pointwise multiplication in the Fourier basis.

The representation theory of the symmetric group is beautifully combinatorial. Each irreducible representation of $S_n$ corresponds to an integer partition of $n$. Has this structure and/or the Fourier transform over the symmetric group found any application in TCS?

$\endgroup$
8

12 Answers 12

29
$\begingroup$

Here are a few other examples.

  1. Diaconis and Shahshahani (1981) studied how many random transpositions are required in order to generate a near uniform permutation. They proved a sharp threshold of 1/2 n log(n) +/- O(n). Generating a Random Permutation with Random Transpositions.

  2. Kassabov (2005) proved that one can build a bounded degree expander on the symmetric group. Symmetric Groups and Expander Graphs.

  3. Kuperberg, Lovett and Peled (2012) proved that there exist small sets of permutations which act uniformly on k-tuples. Probabilistic existence of rigid combinatorial structures.

$\endgroup$
2
  • 3
    $\begingroup$ Thanks Shachar, and welcome to cstheory! I took the liberty to fix your links: they were a bit mismatched $\endgroup$ Sep 23, 2012 at 16:17
  • $\begingroup$ The link to springerlink.com is broken, but the article can be found at doi:10.1007/BF00535487. $\endgroup$
    – user67557
    May 9, 2023 at 14:16
15
$\begingroup$

Here is one example that I know:

``On the 'Log-Rank' Conjecture in Communication Complexity'', R.Raz, B.Spieker,

Proceeding of the 34th FOCS, 1993, pp. 168-177
Combinatorica 15(4) (1995) pp. 567-588 

I believe that there much more.

$\endgroup$
3
  • 3
    $\begingroup$ Could you summarise what the representation models and how it is applied? $\endgroup$
    – Vijay D
    Sep 25, 2012 at 0:56
  • $\begingroup$ @VijayD probably Klim knows more, but the problem here is how the communication complexity of a function $f:\{0,1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$ is related to the log of its rank (thinking of $f$ as a $2^d \times 2^d$ real matrix). They construct an $f$ of rank $2^{O(n)}$ and CC $\Omega(n \log \log n)$. The rank of $f$ is computed by writing it as the sum of matrices in the regular representation of $S_n$ $\endgroup$ Sep 25, 2012 at 13:27
  • $\begingroup$ Actually I read this paper some time ago so now I do not exactly remember it. $\endgroup$
    – Klim
    Sep 28, 2012 at 6:12
14
$\begingroup$

A very good question. I don't know the full answer and would like to know it myself. However, you may find the following interesting. If, instead of the group $S_n$, we consider its 0-Hecke monoid $H_0(S_n)$, it has a representation on a certain class of integer matrices which acts by tropical $(\min,+)$-multiplication. This has a lot of interesting applications in stringology, via multiple-source shortest paths in grid-like graphs. For details, see my technical report:

A. Tiskin. Semi-local string comparison: Algorithmic techniques and applications. http://arxiv.org/abs/0707.3619

$\endgroup$
1
  • $\begingroup$ Thank you! This looks very interesting and I will definitely check it out. $\endgroup$ Sep 26, 2012 at 1:39
13
$\begingroup$

Here's an example from quantum computing:

Roland, Jeremie; Roetteler, Martin; Magnin, Loïck; Ambainis, Andris (2011), "Symmetry-Assisted Adversaries for Quantum State Generation", Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity, CCC '11, IEEE Computer Society, pp. 167–177, doi:10.1109/CCC.2011.24

They show that the quantum query complexity of a certain problem called Index Erasure is $\Omega(\sqrt{n})$ using representation theory of the symmetric group to construct an optimal adversary matrix to plug into the quantum adversary method.

$\endgroup$
12
$\begingroup$
  1. Knuth 3rd volume of The Art of Computer Programming is devoted to searching and sorting and devote much to combinatorics and permutations and to the Robinson-Schensted-Knuth correspondence, which is central in representation theory of the symmetric group.

  2. There are several papers by Ellis-Friedgut-Pilpel, and Ellis-Friedgut-Filmus which solve extremal combinatorial problems using harmonic analysis on $S_n$. Not quite TCS, but quite close.

  3. Ajtai had in the early 90s wonderful results on modular representation of $S_n$ which were motivated by computational complexity questions. I don't remember the details or if it was published, but this is worth perusing!

$\endgroup$
1
  • 1
    $\begingroup$ Thanks Gil! I believe one of the papers by Ajtaj that you have in mind is this one: eccc.hpi-web.de/eccc-reports/1994/TR94-015/index.html. I think the application is to the proof complexity of the pigeonhole principle, but I don't quite understand the connection yet. $\endgroup$ Sep 25, 2012 at 4:20
9
$\begingroup$

The Symmetric Group Defies Strong Fourier Sampling by Moore, Russell, Schulman

"we show that the hidden subgroup problem over the symmetric group cannot be efficiently solved by strong Fourier sampling... These results apply to the special case relevant to the Graph Isomorphism problem."

with a connection to solving the Graph Isomorphism problem via QM approaches

sec 5 Representation theory of the symmetric group

$\endgroup$
7
$\begingroup$

The representation theory of the symmetric group plays a key role in the Geometric Complexity Theory approach to lower bounds on the determinant or on matrix multiplication.

$\endgroup$
6
$\begingroup$

More statistics than computer science, but still interesting: In chapter 8 in Diaconis' monograph on Group Gepresentations in Probability and Statistics, spectral analysis techniques for data associated with a group $G$ are developed. This extends more classical spectral analysis of say time series data where the natural $G$ is the reals or the integers under addition. It makes sense to take $G$ to be $S_n$ when data is given by rankings. The monograph goes into interpreting the Fourier coefficients of ranking data. In that case the data set is represented by a sparse $f:S_n \rightarrow \mathbb{R}^+$ which maps rankings (given by a permutation) to the fraction of the population that prefers the ranking.

Also in the same chapter, Fourier analysis over the symmetric and other groups is used to derive ANOVA models and tests.

A natural extension of this would be statistical learning theory for ranking problems that benefits from representation theoretic techniques in a way similar to the way learning theory for binary classification under the uniform distribution has benefited from Fourier analysis on the boolean cube.

$\endgroup$
2
  • $\begingroup$ What is the natural group structure for ranking problems though ? $\endgroup$ Sep 24, 2012 at 15:29
  • 1
    $\begingroup$ @Suresh I had in mind the symmetric group, but my last paragraph is more wishful thinking than anything else. I had in mind a junta-like problem on rankings: learning a function $f:S_n \rightarrow \{0, 1\}$ that depends on the relative ordering of only a few elements of $[n]$ from few samples. Maybe fourier techniques can give non-trivial sample bounds $\endgroup$ Sep 25, 2012 at 0:12
5
$\begingroup$
$\endgroup$
3
-1
$\begingroup$

Application of the Representation Theory of Symmetric Groups for the Computation of Chromatic Polynomials of Graphs by Klin and Pech

$\endgroup$
1
  • $\begingroup$ ps application— graph coloring $\endgroup$
    – vzn
    Sep 25, 2012 at 4:19
-2
$\begingroup$

this highly cited paper by Beals, 1997, STOC appears to prove that Quantum computation of Fourier transforms over symmetric groups is in BQP ie quantum polynomial time

$\endgroup$
7
  • 2
    $\begingroup$ again this goes with the other quantum paper you refer to. the main motivation for developing the non-abelian Fourier transform was to use it to solve the hidden subgroup problem over the symmetric group. the other paper you cite shows that this approach does not solve the problem. $\endgroup$ Sep 25, 2012 at 1:47
  • $\begingroup$ btw to be clear: what i mean with the above comment is to suggest to merge this answer with the other QM answer and explain how the two are related (because they are) $\endgroup$ Sep 25, 2012 at 15:34
  • $\begingroup$ ok Moore et al cite Beals although thats not how I found the Beals paper. might merge later but right now some audience doesnt seem to like this Beals ref for whatever reason (old, superseded etc...?) $\endgroup$
    – vzn
    Sep 25, 2012 at 18:06
  • $\begingroup$ i am not sure, i think it's an ok reference. one problem for me is that you don't explain why it's important to be able to compute the non-abelian fourier transform, how it's motivated. $\endgroup$ Sep 25, 2012 at 18:10
  • 1
    $\begingroup$ i would prefer if answers stand on their own and give the reader enough of a clue to be able to decide whether to read the full paper or not. i would like the answer to show more than superficial understanding of the material. $\endgroup$ Sep 25, 2012 at 19:12
-5
$\begingroup$

an older example, but still with recent/ongoing research, some of this theory shows up in the mathematics of the "perfect shuffle", seen as an element of the symmetric group & which was a famous discovery at the time. [1] mentions applications of the perfect shuffle to parallel processing algorithms and also the connection to Cooley-Tukey O(n log n) DFT. [2] is more recent. the perfect shuffle shows up in parallel processing [3], memory design, and sorting networks.

[1] Mathematics of the perfect shuffle by Diaconis, Graham, Cantor. 1983

[2] Cycles of the multiway perfect shuffle permutation by Ellis, Fan, Shallit (2002)

[3] Parallel processing with the perfect shuffle by Stone, 1971

[4] Omega network based on perfect shuffling

[5] Parallel and sequential in-place permuting and perfect shuffling using involutions Yang et al (2012)

$\endgroup$
5
  • 1
    $\begingroup$ Is representation theory used in these papers? $\endgroup$ Sep 23, 2012 at 21:55
  • $\begingroup$ seems to be a special case of it $\endgroup$
    – vzn
    Sep 24, 2012 at 3:28
  • 2
    $\begingroup$ what is a special case of what? the perfect shuffle is a permutation. i am asking, is representation theory used in the proofs in these papers? i didn't find any. $\endgroup$ Sep 24, 2012 at 13:45
  • 3
    $\begingroup$ otherwise, there are probabilistic models of (imperfect) shuffling, and repeated shuffling using one of these models is a random walk on permutations. one can sometimes analyze the mixing time of such a random walk using fourier analysis on the symmetric group: Shachar gave one example for the random transpositions shuffle. your references are interesting, but I don't see any connection with representation theory: the papers are concerned with a few (two in [1]) deterministic shuffles and the permutation groups they generate. the analysis seems to be combinatorial $\endgroup$ Sep 24, 2012 at 13:50
  • $\begingroup$ imperfect shuffling is interesting too but the whole pt of the answer is perfect shuffling. appears the above same results could be recast in, or proven via representation theory, or are using some core aspects of it without obvious/direct reference to it. note shachars answer cites Diaconis, same author on one of the papers in this answer. in other words the above authors could surely answer your question better but my expectation is they'd answer at least somewhat in the affirmative =) ... besides you just described representation theory as "beautifully combinatorial" in your own question! $\endgroup$
    – vzn
    Sep 24, 2012 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.