<p>Here is one example that I know: </p>

<p><a href="http://www.wisdom.weizmann.ac.il/~ranraz/publications/Plogrank.ps">``On the 'Log-Rank' Conjecture in Communication Complexity''</a>,
R.Raz, B.Spieker,</p>

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

<p>I believe that there much more.</p>

CC BY-SA 3.0
2012-09-25T00:56:17.390Z
Could you summarise what the representation models and how it  is  applied?
Vijay D
CC BY-SA 3.0
2012-09-25T13:27:26.463Z
@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
CC BY-SA 3.0
2012-09-28T06:12:05.767Z
Actually I read this paper some time ago so now I do not exactly remember it.
Klim
CC BY-SA 3.0
2012-09-23T04:58:22.410Z
2012-09-23T04:58:22.410Z
Klim
<p>Here's an example from quantum computing:</p>

<blockquote>
  <p>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, <a href="http://dx.doi.org/10.1109/CCC.2011.24">doi:10.1109/CCC.2011.24</a></p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2012-09-23T13:01:06.340Z
2012-09-23T13:01:06.340Z
Robin Kothari
<ol>
<li><p>Knuth 3rd volume of <a href="http://rads.stackoverflow.com/amzn/click/0321751043">The Art of Computer Programming</a> is devoted to searching and sorting and devote much to combinatorics and permutations and to the <a href="http://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted%E2%80%93Knuth_correspondence">Robinson-Schensted-Knuth correspondence</a>, which is central in representation theory of the symmetric group.</p></li>
<li><p>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.</p></li>
<li><p>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! </p></li>
</ol>

CC BY-SA 3.0
2012-09-25T04:20:03.910Z
Thanks Gil! I believe one of the papers by Ajtaj that you have in mind is this one: http://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
CC BY-SA 3.0
2012-09-25T00:30:29.843Z
2012-09-25T12:48:37.197Z
2012-09-25T12:48:37.197Z
Gil Kalai
<p>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:</p>

<p>A. Tiskin. Semi-local string comparison: Algorithmic techniques and applications.
<a href="http://arxiv.org/abs/0707.3619">http://arxiv.org/abs/0707.3619</a></p>

CC BY-SA 3.0
2012-09-26T01:39:28.743Z
Thank you! This looks very interesting and I will definitely check it out.
Sasho Nikolov
CC BY-SA 3.0
2012-09-22T08:12:04.120Z
2012-09-22T08:12:04.120Z
Alexander Tiskin
<p><a href="http://arxiv.org/pdf/quant-ph/0501056v3.pdf">The Symmetric Group Defies Strong Fourier Sampling</a> by Moore, Russell, Schulman</p>

<p>"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."</p>

<p>with a connection to solving the Graph Isomorphism problem via QM approaches</p>

<p>sec 5 Representation theory of the symmetric group</p>

CC BY-SA 3.0
2012-09-24T18:52:42.723Z
2012-09-24T18:52:42.723Z
vzn
<p>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.</p>

<ul>
<li><p><a href="http://dx.doi.org/10.1145/2488608.2488627">Bürgisser and Ikenmeyer</a> prove a lower bound on the border-rank of matrix multiplication using the representation theory of $S_n$.</p></li>
<li><p>For how the representation theory of $S_n$ relates to lower bounds on the determinant, see <a href="http://dx.doi.org/10.1137/080718115">Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties</a> and <a href="http://gct.cs.uchicago.edu/gct6.pdf">Geometric Complexity Theory VI: The ﬂip via positivity</a></p></li>
</ul>

CC BY-SA 3.0
2014-03-22T20:57:17.703Z
2014-03-22T20:57:17.703Z
Joshua Grochow
<p>More statistics than computer science, but still interesting: In chapter 8 in Diaconis' monograph on <a href="http://projecteuclid.org/euclid.lnms/1215467407" rel="noreferrer">Group Gepresentations in Probability and Statistics</a>, 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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2012-09-24T15:29:42.080Z
What is the natural group structure for ranking problems though ?
Suresh Venkat
CC BY-SA 3.0
2012-09-25T00:12:05.013Z
@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
CC BY-SA 3.0
2012-09-24T14:31:24.560Z
2012-09-25T00:14:32.123Z
2012-09-25T00:14:32.123Z
Sasho Nikolov
<ul>
<li><p>Huangs Phd thesis, <a href="http://www.select.cs.cmu.edu/publications/paperdir/thesis2011-huang.pdf" rel="nofollow">PROBABILISTIC REASONING AND
LEARNING ON PERMUTATIONS : exploiting structural decompositions of the
symmetric group</a>. the application is "a real camera-based multi-person tracking scenario."</p></li>
<li><p><a href="http://jmlr.csail.mit.edu/papers/volume10/huang09a/huang09a.pdf" rel="nofollow">Fourier Theoretic Probabilistic Inference over Permutations</a> by Huang, Guestrin, Guibas; Journal of Machine Learning Research 10 (2009) 997-1070. see eg sec 5. Representation Theory on the Symmetric Group</p></li>
<li><p>another multitracking application paper. <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.1292" rel="nofollow">Multi-object tracking with representations of the symmetric group (2007)</a> by Kondor, Howard, Jebara</p></li>
<li><p><a href="http://www.sc.ehu.es/ccwbayes/publications/postscript/EHU-KZAA-TR-1-2011.pdf" rel="nofollow">Learning probability distributions over Permutations by Means of Fourier Coefficients,</a> Irurozki, Calvo, Lozano (Dept CS/AI). see sec 2 The Fourier Transform on the Symmetric Group</p></li>
</ul>

CC BY-SA 3.0
2012-09-25T00:15:36.663Z
I'd suggest merging this answer with the other learning permutations reference
Sasho Nikolov
CC BY-SA 3.0
2012-09-25T00:26:04.810Z
ok... merging...
vzn
CC BY-SA 3.0
2012-09-25T15:27:23.710Z
see also [Interpreting the Phase Spectrum in Fourier Analysis of Partial Ranking Data](http://www.hindawi.com/journals/ana/2012/579050/) and [A signal processing approach to Fourier analysis of
ranking data: the importance of phase](http://www3.ntu.edu.sg/home/ramakrishna/bisrank_transsp_final2col.pdf) by Kakarala which seems to extend much earlier work by Diaconis
vzn
CC BY-SA 3.0
2012-09-24T18:43:25.620Z
2012-09-25T00:37:22.973Z
2012-09-25T00:37:22.973Z
vzn
<p><a href="http://www.math.tu-dresden.de/~pech/talks/vortrag2.pdf" rel="nofollow">Application of the Representation Theory of
Symmetric Groups for the Computation of
Chromatic Polynomials of Graphs</a> by Klin and Pech</p>

CC BY-SA 3.0
2012-09-25T04:19:50.910Z
ps application— graph coloring
vzn
CC BY-SA 3.0
2012-09-24T18:01:27.953Z
2012-09-24T18:01:27.953Z
vzn
<p>this highly cited paper by Beals, 1997, STOC appears to prove that <a href="http://libra.msra.cn/Publication/575427/quantum-computation-of-fourier-transforms-over-symmetric-groups" rel="nofollow">Quantum computation of Fourier transforms over symmetric groups</a> is in BQP ie quantum polynomial time</p>

CC BY-SA 3.0
2012-09-25T01:47:05.530Z
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
CC BY-SA 3.0
2012-09-25T15:34:07.613Z
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
CC BY-SA 3.0
2012-09-25T18:06:07.843Z
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
CC BY-SA 3.0
2012-09-25T18:10:38.460Z
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
CC BY-SA 3.0
2012-09-25T18:54:37.437Z
you explained that in the comment. & its explained in the paper .. dont write papers or abstracts, just cite em =)
vzn
CC BY-SA 3.0
2012-09-25T19:12:57.000Z
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
CC BY-SA 3.0
2012-09-25T20:19:48.827Z
uh huh. imho thats largely the pt of an abstract. which is on the pg linked to. chose that one intentionally because there is [another ACM ref](http://dl.acm.org/citation.cfm?id=258548) without the abstract.
vzn
CC BY-SA 3.0
2012-09-25T00:58:34.063Z
2012-09-25T00:58:34.063Z
vzn
<p>an older example, but still with recent/ongoing research, some of this theory shows up in the mathematics of the <a href="http://en.wikipedia.org/wiki/Faro_shuffle" rel="nofollow">"perfect shuffle"</a>, seen as an element of the symmetric group &amp; 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.</p>

<p>[1] <a href="http://www-stat.stanford.edu/~cgates/PERSI/papers/83_05_shuffles.pdf" rel="nofollow">Mathematics of the perfect shuffle</a> by Diaconis, Graham, Cantor. 1983</p>

<p>[2] <a href="http://www.emis.de/journals/DMTCS/pdfpapers/dm050111.pdf" rel="nofollow">Cycles of the multiway perfect shuffle permutation</a> by Ellis, Fan, Shallit (2002)</p>

<p>[3] <a href="http://dl.acm.org/citation.cfm?id=1309584" rel="nofollow">Parallel processing with the perfect shuffle</a> by Stone, 1971</p>

<p>[4] <a href="http://en.wikipedia.org/wiki/Omega_network" rel="nofollow">Omega network</a> based on perfect shuffling</p>

<p>[5] <a href="http://arxiv.org/pdf/1204.1958.pdf" rel="nofollow">Parallel and sequential in-place permuting and perfect shuffling using involutions</a> Yang et al (2012)</p>

CC BY-SA 3.0
2012-09-23T21:55:17.007Z
Is representation theory used in these papers?
Sasho Nikolov
CC BY-SA 3.0
2012-09-24T03:28:06.860Z
seems to be a special case of it
vzn
CC BY-SA 3.0
2012-09-24T13:45:02.803Z
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
CC BY-SA 3.0
2012-09-24T13:50:22.067Z
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
CC BY-SA 3.0
2012-09-24T14:58:54.177Z
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
CC BY-SA 3.0
2012-09-23T18:19:15.703Z
2012-09-23T18:19:15.703Z
vzn
<p>Here are a few other examples. </p>

<ol>
<li><p>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). <a href="http://www.springerlink.com/content/j602u8m7w061467r/fulltext.pdf">Generating a Random Permutation with Random Transpositions</a>.</p></li>
<li><p>Kassabov (2005) proved that one can build a bounded degree expander on the symmetric group. <a href="http://arxiv.org/abs/math.GR/0505624">Symmetric Groups and Expander Graphs</a>.</p></li>
<li><p>Kuperberg, Lovett and Peled (2012) proved that there exist small sets of permutations which act uniformly on k-tuples. <a href="http://arxiv.org/abs/1111.0492">Probabilistic existence of rigid combinatorial structures</a>.</p></li>
</ol>

CC BY-SA 3.0
2012-09-23T16:17:24.073Z
Thanks Shachar, and welcome to cstheory! I took the liberty to fix your links: they were a bit mismatched
Sasho Nikolov
CC BY-SA 3.0
2012-09-23T15:28:23.400Z
2012-09-23T16:15:54.667Z
2012-09-23T16:15:54.667Z
Shachar Lovett
<p>Inspired by <a href="https://cstheory.stackexchange.com/questions/12678/why-does-fourier-analysis-of-boolean-functions-work">this question</a> and in particular the final paragraph of Or's answer, I have the following question:</p>

<blockquote>
  <p>Do you know of any applications of the representation theory of the symmetric group in TCS?</p>
</blockquote>

<p>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 <a href="http://en.wikipedia.org/wiki/Fourier_transform_on_finite_groups" rel="noreferrer">Fourier transform over non-abelian groups</a>. 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.</p>

<p>The <a href="http://en.wikipedia.org/wiki/Representation_theory_of_the_symmetric_group" rel="noreferrer">representation theory of the symmetric group</a> is beautifully combinatorial. Each irreducible representation of $S_n$ corresponds to an integer partition of $n$. <em>Has this structure and/or the Fourier transform over the symmetric group found any application in TCS?</em> </p>

CC BY-SA 3.0
2012-09-23T15:23:01.733Z
see also [applications of the symmetric group](http://en.wikipedia.org/wiki/Symmetric_group#Applications), wikipedia
vzn
CC BY-SA 3.0
2012-09-23T16:23:39.213Z
all very interesting answers. i am going to have a hard time choosing one to accept.
Sasho Nikolov
CC BY-SA 3.0
2012-09-24T21:11:21.453Z
decent purely theoretical introduction/overview, [Young Tableaux and the Representations
of the Symmetric Group, by Zhao](http://www.thehcmr.org/issue2_2/tableaux.pdf)
vzn
CC BY-SA 3.0
2012-09-25T03:11:27.553Z
This paper just hit the quant-ph arXiv: [A solution to two party typicality using representation theory of the symmetric group](http://arxiv.org/abs/1209.5094) by Janis Noetzel.
Tyson Williams
CC BY-SA 3.0
2012-09-25T16:17:30.477Z
[Symmetry-Based Matrix factorization by Egner and Puschel](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.280) uses elements of $S_n$ and representation theory for efficient matrix factorization/decomposition/multiplication. see S3.2 on Perm-Perm symmetry.
vzn
CC BY-SA 3.0
2012-09-25T18:34:16.207Z
example use of Young tableaux [corresponding to the integer partitions] to analyze/decompose random sorting networks. [A PATTERN THEOREM FOR RANDOM SORTING
NETWORKS](http://research.microsoft.com/en-us/um/people/holroyd/papers/pattern.pdf) and [Random Sorting Networks](http://arxiv.org/pdf/math/0609538v1.pdf) Angel, Holroyd
vzn
CC BY-SA 3.0
2012-09-26T01:42:00.860Z
I am accepting Shachar's answer as the most upvoted one. But *all* references I got were very interesting - thanks!
Sasho Nikolov
CC BY-SA 3.0
2014-03-29T02:11:48.990Z
this paper seems to use it esp section 5 starting p22 [Boolean functions, invariance groups & parallel complexity](http://clavius.bc.edu/~clote/pub/cloteKranakisBooleanFunctions.pdf) Clote/Kranakis
vzn
<co.combinatorics><permutations><fourier-analysis><gr.group-theory>
Applications of representation theory of the symmetric group
Sasho Nikolov
# Applications of representation theory of the symmetric group

(Asked by: username_0 on 2012-09-22)

Inspired by [this question](https://cstheory.stackexchange.com/questions/12678/why-does-fourier-analysis-of-boolean-functions-work) 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](http://en.wikipedia.org/wiki/Fourier_transform_on_finite_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](http://en.wikipedia.org/wiki/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?*

**Tags:** co.combinatorics, permutations, fourier-analysis, gr.group-theory

> **Comments:**
> **username_1**: see also [applications of the symmetric group](http://en.wikipedia.org/wiki/Symmetric_group#Applications), wikipedia  
> **username_0**: all very interesting answers. i am going to have a hard time choosing one to accept.  
> **username_1**: decent purely theoretical introduction/overview, [Young Tableaux and the Representations of the Symmetric Group, by Zhao](http://www.thehcmr.org/issue2_2/tableaux.pdf)  
> **username_2**: This paper just hit the quant-ph arXiv: [A solution to two party typicality using representation theory of the symmetric group](http://arxiv.org/abs/1209.5094) by Janis Noetzel.  
> **username_1**: [Symmetry-Based Matrix factorization by Egner and Puschel](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.280) uses elements of $S_n$ and representation theory for efficient matrix factorization/decomposition/multiplication. see S3.2 on Perm-Perm symmetry.  
> **username_1**: example use of Young tableaux [corresponding to the integer partitions] to analyze/decompose random sorting networks. [A PATTERN THEOREM FOR RANDOM SORTING NETWORKS](http://research.microsoft.com/en-us/um/people/holroyd/papers/pattern.pdf) and [Random Sorting Networks](http://arxiv.org/pdf/math/0609538v1.pdf) Angel, Holroyd  
> **username_0**: I am accepting Shachar's answer as the most upvoted one. But *all* references I got were very interesting - thanks!  
> **username_1**: this paper seems to use it esp section 5 starting p22 [Boolean functions, invariance groups & parallel complexity](http://clavius.bc.edu/~clote/pub/cloteKranakisBooleanFunctions.pdf) Clote/Kranakis  

---

## 12 answers

### Answer by username_10 on 2012-09-23. Score: 30 | Accepted answer

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](http://www.springerlink.com/content/j602u8m7w061467r/fulltext.pdf).
2. Kassabov (2005) proved that one can build a bounded degree expander on the symmetric group. [Symmetric Groups and Expander Graphs](http://arxiv.org/abs/math.GR/0505624).
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](http://arxiv.org/abs/1111.0492).

> **Comments:**
> **username_0**: Thanks Shachar, and welcome to cstheory! I took the liberty to fix your links: they were a bit mismatched  

---

### Answer by username_3 on 2012-09-23. Score: 16

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.

> **Comments:**
> **username_4**: Could you summarise what the representation models and how it  is  applied?  
> **username_0**: @VijayD probably username_3 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$  
> **username_3**: Actually I read this paper some time ago so now I do not exactly remember it.  

---

### Answer by username_7 on 2012-09-22. Score: 15

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>

> **Comments:**
> **username_0**: Thank you! This looks very interesting and I will definitely check it out.  

---

### Answer by username_5 on 2012-09-23. Score: 13

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](http://dx.doi.org/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.


---

### Answer by username_6 on 2012-09-25. Score: 12

1. Knuth 3rd volume of [The Art of Computer Programming](http://rads.stackoverflow.com/amzn/click/0321751043) is devoted to searching and sorting and devote much to combinatorics and permutations and to the [Robinson-Schensted-Knuth correspondence](http://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted%E2%80%93Knuth_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!

> **Comments:**
> **username_0**: Thanks Gil! I believe one of the papers by Ajtaj that you have in mind is this one: http://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.  

---

### Answer by username_1 on 2012-09-24. Score: 9

[The Symmetric Group Defies Strong Fourier Sampling](http://arxiv.org/pdf/quant-ph/0501056v3.pdf) 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


---

### Answer by username_8 on 2014-03-22. Score: 7

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.

* [Bürgisser and Ikenmeyer](http://dx.doi.org/10.1145/2488608.2488627) prove a lower bound on the border-rank of matrix multiplication using the representation theory of $S\_n$.
* For how the representation theory of $S\_n$ relates to lower bounds on the determinant, see [Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties](http://dx.doi.org/10.1137/080718115) and [Geometric Complexity Theory VI: The ﬂip via positivity](http://gct.cs.uchicago.edu/gct6.pdf)


---

### Answer by username_0 on 2012-09-24. Score: 6

More statistics than computer science, but still interesting: In chapter 8 in Diaconis' monograph on [Group Gepresentations in Probability and Statistics](http://projecteuclid.org/euclid.lnms/1215467407), 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.

> **Comments:**
> **username_9**: What is the natural group structure for ranking problems though ?  
> **username_0**: @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  

---

### Answer by username_1 on 2012-09-24. Score: 5

* Huangs Phd thesis, [PROBABILISTIC REASONING AND
  LEARNING ON PERMUTATIONS : exploiting structural decompositions of the
  symmetric group](http://www.select.cs.cmu.edu/publications/paperdir/thesis2011-huang.pdf). the application is "a real camera-based multi-person tracking scenario."
* [Fourier Theoretic Probabilistic Inference over Permutations](http://jmlr.csail.mit.edu/papers/volume10/huang09a/huang09a.pdf) by Huang, Guestrin, Guibas; Journal of Machine Learning Research 10 (2009) 997-1070. see eg sec 5. Representation Theory on the Symmetric Group
* another multitracking application paper. [Multi-object tracking with representations of the symmetric group (2007)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.1292) by Kondor, Howard, Jebara
* [Learning probability distributions over Permutations by Means of Fourier Coefficients,](http://www.sc.ehu.es/ccwbayes/publications/postscript/EHU-KZAA-TR-1-2011.pdf) Irurozki, Calvo, Lozano (Dept CS/AI). see sec 2 The Fourier Transform on the Symmetric Group

> **Comments:**
> **username_0**: I'd suggest merging this answer with the other learning permutations reference  
> **username_1**: ok... merging...  
> **username_1**: see also [Interpreting the Phase Spectrum in Fourier Analysis of Partial Ranking Data](http://www.hindawi.com/journals/ana/2012/579050/) and [A signal processing approach to Fourier analysis of ranking data: the importance of phase](http://www3.ntu.edu.sg/home/ramakrishna/bisrank_transsp_final2col.pdf) by Kakarala which seems to extend much earlier work by Diaconis  

---

### Answer by username_1 on 2012-09-24. Score: -1

[Application of the Representation Theory of
Symmetric Groups for the Computation of
Chromatic Polynomials of Graphs](http://www.math.tu-dresden.de/~pech/talks/vortrag2.pdf) by Klin and Pech

> **Comments:**
> **username_1**: ps application— graph coloring  

---

### Answer by username_1 on 2012-09-25. Score: -2

this highly cited paper by Beals, 1997, STOC appears to prove that [Quantum computation of Fourier transforms over symmetric groups](http://libra.msra.cn/Publication/575427/quantum-computation-of-fourier-transforms-over-symmetric-groups) is in BQP ie quantum polynomial time

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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)  
> **username_1**: 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...?)  
> **username_0**: 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.  
> **username_1**: you explained that in the comment. & its explained in the paper .. dont write papers or abstracts, just cite em =)  
> **username_0**: 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.  
> **username_1**: uh huh. imho thats largely the pt of an abstract. which is on the pg linked to. chose that one intentionally because there is [another ACM ref](http://dl.acm.org/citation.cfm?id=258548) without the abstract.  

---

### Answer by username_1 on 2012-09-23. Score: -5

an older example, but still with recent/ongoing research, some of this theory shows up in the mathematics of the ["perfect shuffle"](http://en.wikipedia.org/wiki/Faro_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](http://www-stat.stanford.edu/~cgates/PERSI/papers/83_05_shuffles.pdf) by Diaconis, Graham, Cantor. 1983

[2] [Cycles of the multiway perfect shuffle permutation](http://www.emis.de/journals/DMTCS/pdfpapers/dm050111.pdf) by Ellis, Fan, Shallit (2002)

[3] [Parallel processing with the perfect shuffle](http://dl.acm.org/citation.cfm?id=1309584) by Stone, 1971

[4] [Omega network](http://en.wikipedia.org/wiki/Omega_network) based on perfect shuffling

[5] [Parallel and sequential in-place permuting and perfect shuffling using involutions](http://arxiv.org/pdf/1204.1958.pdf) Yang et al (2012)

> **Comments:**
> **username_0**: Is representation theory used in these papers?  
> **username_1**: seems to be a special case of it  
> **username_0**: 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.  
> **username_0**: 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  
> **username_1**: 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!  

---

