Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
see also applications of the symmetric group, wikipedia –  vzn Sep 23 '12 at 15:23
    
all very interesting answers. i am going to have a hard time choosing one to accept. –  Sasho Nikolov Sep 23 '12 at 16:23
    
decent purely theoretical introduction/overview, Young Tableaux and the Representations of the Symmetric Group, by Zhao –  vzn Sep 24 '12 at 21:11
2  
This paper just hit the quant-ph arXiv: A solution to two party typicality using representation theory of the symmetric group by Janis Noetzel. –  Tyson Williams Sep 25 '12 at 3:11
    
Symmetry-Based Matrix factorization by Egner and Puschel uses elements of $S_n$ and representation theory for efficient matrix factorization/decomposition/multiplication. see S3.2 on Perm-Perm symmetry. –  vzn Sep 25 '12 at 16:17
show 3 more comments

12 Answers 12

up vote 23 down vote accepted

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.

share|improve this answer
3  
Thanks Shachar, and welcome to cstheory! I took the liberty to fix your links: they were a bit mismatched –  Sasho Nikolov Sep 23 '12 at 16:17
add comment

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

share|improve this answer
    
Thank you! This looks very interesting and I will definitely check it out. –  Sasho Nikolov Sep 26 '12 at 1:39
add comment

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.

share|improve this answer
1  
Could you summarise what the representation models and how it is applied? –  Vijay D Sep 25 '12 at 0:56
    
@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$ –  Sasho Nikolov Sep 25 '12 at 13:27
    
Actually I read this paper some time ago so now I do not exactly remember it. –  Klim Sep 28 '12 at 6:12
add comment

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.

share|improve this answer
add comment
  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!

share|improve this answer
    
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. –  Sasho Nikolov Sep 25 '12 at 4:20
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
What is the natural group structure for ranking problems though ? –  Suresh Venkat Sep 24 '12 at 15:29
1  
@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 –  Sasho Nikolov Sep 25 '12 at 0:12
add comment
share|improve this answer
1  
I'd suggest merging this answer with the other learning permutations reference –  Sasho Nikolov Sep 25 '12 at 0:15
    
ok... merging... –  vzn Sep 25 '12 at 0:26
    
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
ps application— graph coloring –  vzn Sep 25 '12 at 4:19
add comment

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

share|improve this answer
2  
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. –  Sasho Nikolov Sep 25 '12 at 1:47
    
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) –  Sasho Nikolov Sep 25 '12 at 15:34
    
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...?) –  vzn Sep 25 '12 at 18:06
    
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. –  Sasho Nikolov Sep 25 '12 at 18:10
1  
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. –  Sasho Nikolov Sep 25 '12 at 19:12
show 2 more comments

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)

share|improve this answer
1  
Is representation theory used in these papers? –  Sasho Nikolov Sep 23 '12 at 21:55
    
seems to be a special case of it –  vzn Sep 24 '12 at 3:28
2  
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. –  Sasho Nikolov Sep 24 '12 at 13:45
3  
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 –  Sasho Nikolov Sep 24 '12 at 13:50
    
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! –  vzn Sep 24 '12 at 14:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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