arXiv:1704.06299v3 [math.CO] 8 Mar 2018

Complexity of the Fourier transform
on the Johnson graph
Rodrigo Iglesias

Mauro Natale

Departamento de Matemática
Universidad Nacional del Sur
Bahı́a Blanca, Argentina.

Facultad de Ciencias Exactas
Universidad Nacional del Centro
Tandil, Argentina.

March 9, 2018
Abstract
The set X of k-subsets of an n-set has a natural graph structure where two
k-subsets are connected if and only if the size of their intersection is k − 1. This
is known as the Johnson graph. The symmetric group Sn acts on the space of
complex functions on X and this space has a multiplicity-free decomposition as
sum of irreducible representations of Sn , so it has a well-defined Gelfand-Tsetlin
basis up to scalars. The Fourier transform on the Johnson graph is defined as the
change of basis matrix from the delta function basis to the Gelfand-Tsetlin
basis.
2
The direct application of this matrix to a generic vector requires nk arithmetic
operations. We show that –in analogy with the classical Fast Fourier Transform on
the discrete circle– this matrix can be factorized as a product of n − 1 orthogonal
matrices, each one with at most two nonzero elements in each column. This factorization shows that the number of arithmetic operations required to apply this
matrix to a generic vector is bounded above by 2(n − 1) nk . As a consequence, we
show that the problem of computing all the weights of the irreducible components
of a given function
can be solved in O(n nk ) operations, improving the previous

√
bound O(k 2 nk ) when k asymptotically dominates n in a non-uniform model of
computation. The same improvement is achieved for the problem of computing the
isotypic projection onto a single component.
The proof is based on the construction of n − 1 intermediate bases, each one
parametrized by certain pairs composed by a standard Young tableau and a word.
The parametrization of each basis is obtained via the Robinson-Schensted insertion
algorithm.

1

Introduction

The set of all subsets of cardinality k of a set of cardinality n is a basic combinatorial
object with a natural metric space structure where two k-subsets are at distance d if the
size of their intersection is k − d. This structure is captured by the Johnson graph J(n, k),
whose nodes are the k-subsets and two k-subsets are connected if and only if they are at
distance 1.
1

The Johnson graph is closely related to the Johnson scheme, an association scheme of
major significance in classical coding theory (see [5] for a survey on association scheme
theory and its application to coding theory). Recently, the Johnson graph played a
fundamental role in the breakthrough quasipolynomial time algorithm for the graph isomorphism problem presented in [2] (see [15] for background on the graph isomorphism
problem).
Functions on the Johnson graph arise in the analysis of ranked data. In many contexts,
agents choose a k-subset from an n-set, and the data is collected as the function that
assigns to the k-subset x the number of agents who choose x. This situation is considered,
for example, in the statistical analysis of certain lotteries (see [7], [8]).
The vector space of functions on the Johnson graph is a representation of the symmetric group and it decomposes as a multiplicity-free direct sum of irreducible representations
(see [14]). Statistically relevant information about the function is contained in the isotypic projections of the function onto each irreducible component. This approach to the
analysis of ranked data was called spectral analysis by Diaconis and developed in [6], [7].
The problem of the efficient computation of the isotypic projections has been studied by
Diaconis and Rockmore in [8], and by Maslen, Orrison and Rockmore in [12].
The classical Discrete Fourier Transform (DFT) on the cyclic group Z/2n Z can be
seen as the application of a change of basis matrix from the basis B0 of delta functions to
the basis Bn of characters of the group Z/2n Z. The direct application of this matrix to a
generic vector involves (2n )2 arithmetic operations. The Fast Fourier Transform (FFT) is
a fundamental algorithm that computes the DFT in O(n2n ) operations. This algorithm
was discovered by Cooley and Tukey [4] and the efficiency of their algorithm is due to a
factorization of the change of basis matrix
[B0 ]Bn = [Bn−1 ]Bn ... [B1 ]B2 [B0 ]B1
where B1 , ..., Bn−1 are intermediate orthonormal bases such that each matrix [Bi−1 ]Bi has
two nonzero entries in each column.
In this paper, we show that the same phenomenon occurs in the case of the non-abelian
Fourier transform on the Johnson graph. This transform is defined as the application of
the change of basis matrix from the basis B0 of delta functions to the basis Bn of GelfandTsetlin functions. The Gelfand-Tsetlin basis –defined in Section 2– is well-behaved with
respect to the action of the symmetric group Sn , in the sense that each irreducible component is generated by a subset of the basis.
2
A direct computation of this Fourier transform involves nk arithmetic operations.
The computational model used here counts a single complex multiplication and addition
as one operation. We construct intermediate orthonormal bases B1 , ..., Bn−1 such that
each change of basis matrix [Bi−1 ]Bi has at most two nonzero entries in each column.
Each intermediate basis Bi is parametrized by pairs composed by a standard Young
tableau of height at most two and a word in the alphabet {1, 2} as shown in Figure 1.
These intermediate bases enable the computation
of the non-abelian Fourier transform

n
–as well as its inverse– in at most 2(n − 1) k operations.
The upper bound we obtained for the algebraic complexity of the Fourier transform on
the Johnson graph can be applied to the well-studied problem of computing the isotypic
components of a function. The most efficient algorithm for computing all the isotypic
2

Figure 1: Labels of the intermediate bases in the case n = 4, k = 2. The i-th column
parametrize the basis Bi .

components –given by Maslen,
Orrison and Rockmore in [12]– relies on Lanczos iteration

2 n
method and uses O(k k ) operations.
But if the problem were to compute the isotypic projection onto a single component,
it is no clear how to reduce this upper bound using the algorithm in [12]. We show that
-once the intermediate matrices [Bi−1
 ]Bi have been computed for a fixed pair (n, k)– this
task can be accomplished in O(n nk√) operations, so our upper bound is an improvement
when k asymptotically dominates n.
We point out that this is an improvement only within the non-uniform setting, in
the sense that our results imply the existence of smaller arithmetic circuits for each pair
(n, k), but we do not present an algorithm to find each circuit because we do not give
an algorithm to find the intermediate matrices [Bi−1 ]Bi . We refer to [13] (Section 11.4),
[1] (Chapter 14) and [3] for an introduction to non-uniform models of computation and
arithmetic circuits.

We also show that the same O(n nk ) bound is achieved for the problem of computing
all the weights of the irreducible components appearing in the decomposition of a function.
This problem could also be solved by computing every
isotypic component and measuring

2 n
their lengths, but this approach requires O(k k ) operations if we use the algorithm in
[12].
In Section 2, we review the definition of Gelfand-Tsetlin bases for representations of
the symmetric group. In Section 3, we describe the well-known decomposition of the
function space on the Johnson graph and define the corresponding Gelfand-Tsetlin basis.
In Section 4, we introduce the sequence of intermediate bases of the function space, we
analyze the sparsity of the change of basis matrix between two consecutive bases and then
we prove the main result, contained in Theorem 2. In Section 5 we point out the relation
3

of our algorithm with the Robinson-Schensted insertion algorithm. In Section 6 we apply
our algorithm to the problem of the computation of the isotypic components of a function
on the Johnson graph. Finally, in Section 7 we propose a problem for future work.

2

Gelfand-Tsetlin bases

Consider the chain of subgroups of Sn
S1 ⊂ S2 ⊂ S3 ... ⊂ Sn
where Sk is the subgroup of those permutations fixing the last n − k elements of {1, ..., n}.
Let Irr(n) be the set of equivalence classes of irreducible complex representations of Sn .
A fundamental fact in the representation theory of Sn is that if Vλ is an irreducible Sn module corresponding to the representation λ ∈ Irr(n) and we consider it by restriction
as an Sn−1 -module, then it decomposes as sum of irreducible representations of Sn−1 in
a multiplicity-free way (see for example [16]). This means that if Vµ is an irreducible
Sn−1 -module corresponding to the representation µ ∈ Irr(n − 1) then the dimension of
the space HomSn−1 (Vµ , Vλ ) is 0 or 1. The branching graph is the following directed graph.
The set of nodes is the disjoint union
G
Irr(n).
n≥1

Given representations λ ∈ Irr(n) and µ ∈ Irr(n − 1) there is an edge connecting them if
and only if µ appears in the decomposition of λ, that is, if dim HomSn−1 (Vµ , Vλ ) = 1. If
there is an edge between them we write
µ % λ,
so we have a canonical decomposition of Vλ into irreducible Sn−1 -modules
M
Vλ =
Vµ .
µ%λ

Applying this formula iteratively we obtain a uniquely determined decomposition into
one-dimensional subspaces
M
Vλ =
VT ,
T

where T runs over all chains
T = λ1 % λ2 % ... % λn ,
with λi ∈ Irr(i) and λn = λ. Choosing a unit vector vT –with respect to the Sn -invariant
inner product in Vλ – of the one-dimensional space VT we obtain a basis {vT } of the
irreducible module Vλ , which is called the Gelfand-Tsetlin basis.
Observe that if V is a multiplicity-free representation of Sn then there is a uniquely
determined –up to scalars– Gelfand-Tsetlin basis of V . In effect, if
M
V =
Vλ
λ∈S⊆Irr(n)

4

and Bλ is a GT-basis of Vλ then a GT-basis of V is given by the disjoint union
G
B=
Bλ .
λ∈S⊆Irr(n)

The Young graph is the directed graph where the nodes are the Young diagrams and
there is an arrow from λ to µ if and only if λ is contained in µ and their difference consists
in only one box. It turns out that the branching graph is isomorphic to the Young graph
and there is a bijection between the set of Young diagrams with n boxes and Irr(n)
(Theorem 5.8 of [16]).
Then there is a bijection between the Gelfand-Tsetlin basis of Vλ –where λ is a Young
diagram– and the set of paths in the Young graph starting at the one-box diagram and
ending at the diagram λ. Each path can be represented by a unique standard Young
tableau, so that the Gelfand-Tsetlin-basis of Vλ is parametrized by the set of standard
Young tableaux of shape λ (see Figure 2). From now on we identify a chain λ1 % λ2 %
... % λn with its corresponding standard Young tableau.

Figure 2: The Young graph. Each path from the top node to a particular Young diagram
λ is identified with a standard Young tableau of shape λ.

3

Decomposition of the function space on the Johnson graph

We define a k-set as a subset of {1, ..., n} of cardinality k. Let X be the set of all k-sets.
Given two k-sets x, y the distance d(x, y) is defined as n − |x ∩ y|. The group Sn acts
naturally on X by
σ{i1 , ..., ik } = {σ(i1 ), ..., σ(ik )}
The vector space F of the complex valued functions on X is a complex representation of
Sn where the action is given by σf = f ◦ σ −1 .
5

To each k-set x ∈ X we attach the delta function δ(x) defined on X by

1 if x = z
δ(x)(z) =
.
0 otherwise
We consider F as an inner product space where the inner product is such that the
delta functions form an orthonormal basis.
A Young diagram can be identified with the sequence given by the numbers of boxes
in the rows, written top down. For example the Young diagram

is identified with (5, 4, 2). It can be shown (see [14]) that the decomposition of F as a
direct sum of irreducible representations of Sn is given as follows.
From now on we denote by s the number min(k, n − k).
Theorem 1. The space F of functions on the Johnson graph J(n,k) decomposes in s + 1
multiplicity-free irreducible representations of the group Sn . Moreover, the decomposition
is given by
s
M
F=
Vαi
i=0

where αi is the Young diagram (n − i, i).
For example, if n = 6 and k = 2 then the irreducible components of F are in correspondence with the Young diagrams

3.1

Gelfand-Tsetlin basis of F

From Theorem 1 we see that F has a well-defined –up to scalars– Gelfand-Tsetlin basis
and that there is a bijection between the set of elements of this GT-basis and the set of
standard tableaux of shape (n − a, a) where a runs from 0 to s.
Let us give a more explicit description of the GT-basis of F. Consider the space F as
an Si -module for i = 1, ..., n, and let Fi,λ be the isotypic component corresponding to the
irreducible representation λ of Si so that for each i we have a decomposition
M
F=
Fi,λ
λ∈Irr(Si )

where Fi,λ ⊥ Fi,λ0 if λ 6= λ0 . For each standard tableau λ1 % λ2 % ... % λn let
Fλ1 %λ2 %...%λn = F1,λ1 ∩ F2,λ2 ∩ ... ∩ Fn,λn
Then Theorem 1 shows that F has an orthogonal decomposition in one-dimensional subspaces
M
F=
Fλ1 %λ2 %...%λn
λ1 %λ2 %...%λn

where λn runs through all representations of Sn corresponding to Young diagrams (n−a, a)
for a = 0, ..., s (see Figure 3).
6

Figure 3: The leaves of this tree parametrize the Gelfand-Tsetlin basis of the space F of
functions on the Johnson graph J(4, 2).

4

The intermediate bases

Let us describe schematically the Fast Fourier Transform algorithm for the Johnson graph.
The input is a vector f in the space F of functions on the set X of k-sets, written in the
delta function basis B0 , given as a column vector [f ]B0 . The output of the algorithm is
a column vector representing the vector f written in the basis Bn , the Gelfand-Tsetlin
basis of F. In other words, the objective is to apply the change of basis matrix to a given
column vector:
[f ]Bn = [B0 ]Bn [f ]B0
Our technique to realize this matrix multiplication is to construct a sequence of intermediate orthonormal bases B1 , B2 , ..., Bn−1 such that
[B0 ]Bn = [B0 ]B1 [B1 ]B2 ... [Bn−1 ]Bn
is a decomposition where each factor is a very sparse matrix.

4.1

Definition of the basis Bi

We represent a k-set by a word in the alphabet {1, 2} as follows. The element i ∈ {1, ..., n}
belongs to the k-subset if and only if the place i of the word is occupied by the letter 1.
For example,
{2, 3, 6, 8} ⊆ {1, ..., 9}
→
211221212
So, from now on, we identify X with the set of words of length n in the alphabet {1, 2}
such that the letter 1 appears k times. The group Sn acts on X in the natural way.
The subgroup Si with 1 ≤ i ≤ n acts on the first i letters fixing the last n − i letters
of the word. Let Xi be the set of words –in the alphabet {1, 2}– of length n − i where the
letter 1 appears k times or less.

7

For each w ∈ Xi we define X w as the subset of those words x ∈ X that consist of
a concatenation x = w0 w for some word w0 of length i. Observe that each subset X w is
stabilized by the action of the subgroup Si .
Let F w be the subspace of F spanned by the delta functions δ(x) such that x ∈ X w :
M
Fw =
C δ(x).
x∈X w

Then F decomposes as
F=

M

Fw

w∈Xi
w

and each subspace F is invariant by the action of Si .
The following is a key observation. Suppose that the letter 1 appears k − r times in
the word w, where 0 ≤ r ≤ k. Then the subset X w consists of those words of the form
w0 w such that w0 is of length i and it has exactly r appearances of the letter 1. This
means that X w has the structure of the Johnson graph J(i, r) and, when acted by the
subgroup Si , the space of C-valued functions on X w decomposes as an Si -module in a
multiplicity-free way according to the formula of Theorem 1.
As a consequence, each subspace F w has a Gelfand-Tsetlin decomposition
M
Fw =
Fλw1 %λ2 %...%λi ,
λ1 %λ2 %...%λi

where λi runs over all Young diagrams (i − a, a) with 0 ≤ a ≤ min(r, i − r). Then F w has
a Gelfand-Tsetlin basis B w , uniquely determined up to scalars. We define, up to scalars,
the i-th intermediate basis of F as
G
Bw.
Bi =
w∈Xi

From Theorem 1, we see that the basis B w is parametrized by the set of standard
tableaux of shape (i − a, a) with 0 ≤ a ≤ min(r, i − r). On the other hand, the word w
runs over the set Xi . Figure 4 illustrates the structure of the intermediate bases.

4.2

Sparsity of the change of basis matrix [Bi ]Bi−1

Let Fi,λ be defined as in Section 3.1. On the other hand, for i = 1, ..., n and c ∈ {1, 2} let
us define F i,c as the subspace of F generated by the delta functions δ(x) such that the
word x has the letter c in the place i. For each i we have a decomposition
F = F i,1 ⊕ F i,2
with F i,1 ⊥ F i,2 . Let w ∈ Xi
w = ci+1 ci+2 ...cn .
Then
F w = F i+1,ci+1 ∩ ... ∩ F n−1,cn−1 ∩ F n,cn

8

Figure 4: Labels of the intermediate bases in the case n = 4, k = 2. The boxes in each
column represent the decomposition Bi = tw∈Xi B w .

and the one-dimensional subspaces generated by elements of the base Bi can be expressed
as
Fλw1 %λ2 %...%λi = F1,λ1 ∩ F2,λ2 ∩ ... ∩ Fi,λi ∩ F i+1,ci+1 ∩ ... ∩ F n−1,cn−1 ∩ F n,cn .
Let us compare the base Bi with the base Bi−1 .
Definition 1. Let b ∈ Bi−1 and b0 ∈ Bi . We say that b and b0 are related if both belong
to the subspace
F1,λ1 ∩ ... ∩ Fi−1,λi−1 ∩ F i+1,ci+1 ∩ ... ∩ F n,cn
for some Young diagrams λ1 , ..., λi−1 and some letters ci+1 , ..., cn in {1, 2}.
Lemma 1. Suppose that the subspace
F1,λ1 ∩ ... ∩ Fi−1,λi−1 ∩ Fi,λi ∩ F i+1,ci+1 ∩ ... ∩ F n,cn
generated by an element of the basis Bi is not orthogonal to the subspace
0

0

0

F1,λ01 ∩ ... ∩ Fi−1,λ0i−1 ∩ F i,ci ∩ F i+1,ci+1 ∩ ... ∩ F n,cn
generated by an element of the basis Bi−1 . Then
λ1 = λ01 , ... , λi−1 = λ0i−1

and

ci+1 = c0i+1 , ... , cn = c0n .

Proof. If λj 6= λ0j for some j with 1 ≤ j ≤ i − 1, then
Fj,λj ⊥ Fj,λ0j
9

and the two subspaces are orthogonal. If cj 6= c0j for some j with i + 1 ≤ j ≤ n, then
0

F j,cj ⊥ F j,cj
and the two subspaces are orthogonal.
It is immediate that Lemma 1 is equivalent to the following.
Corollary 1. If b ∈ Bi−1 and b0 ∈ Bi are not orthogonal then they are related.
Corollary 2. For each element b of the base Bi there is at most two elements of the base
Bi−1 not orthogonal to b.
Proof. Suppose that the element b of Bi generates the subspace
F1,λ1 ∩ ... ∩ Fi−1,λi−1 ∩ Fi,λi ∩ F i+1,ci+1 ∩ ... ∩ F n,cn .
By Lemma 1, the subspace generated by an element of Bi−1 not orthogonal to b is of the
form
F1,λ1 ∩ ... ∩ Fi−1,λi−1 ∩ F i,ci ∩ F i+1,ci+1 ∩ ... ∩ F n,cn ,
where ci = 1 or ci = 2.
Theorem 2. Let B0 be the delta function basis of F and let Bn be a Gelfand-Tsetlin basis
of F. We assume that the matrices [Bi−1 ]Bi for i = 2, 3, ..., n have been computed. Then,
given a column vector [f ]B0 with f ∈ F, the column vector [f ]Bn given by
[f ]Bn = [B0 ]Bn [f ]B0

can be computed using at most 2(n − 1) nk operations.
Proof. By Corollary 2 we see that each column of the matrix [Bi−1 ]Bi has at most two
non-zero elements. Then the application
of the matrix [Bi−1 ]Bi to a generic column vector

n
can be done using at most 2 k operations. Observe that [B0 ]B1 is the identity matrix.
We have
[B0 ]Bn = [B0 ]B1 [B1 ]B2 ... [Bn−1 ]Bn = [B1 ]B2 ... [Bn−1 ]Bn .
Then the successive applications of the n − 1 matrices can be done in at most 2(n − 1)
operations.

4.3

n
k



Example

Consider the case n = 4, k = 2. For each vector b of the basis Bi , there exists a
unique word w ∈ Xi and a unique standard tableau λ1 % λ2 % ... % λi such that
b ∈ Fλw1 %λ2 %...%λi . Then b is a linear combination of those elements of Bi−1 that belong
to the space Fλw̄1 %λ2 %...%λi−1 , where w̄ = 1w or w̄ = 2w. Then the matrices [Bi ]Bi−1 have
the form

10



[B1 ]B2




=




∗
0
0
0
0
0

0
∗
∗
0
0
0

0
∗
∗
0
0
0

0
0
0
∗
∗
0

0
0
0
∗
∗
0

0
0
0
0
0
∗


[B3 ]B4




=
















[B2 ]B3




=




0
0
∗
0
0
∗

∗
0
0
0
∗
0

∗
0
0
0
∗
0

0
∗
0
∗
0
0

0
∗
0
∗
0
0

0
0
∗
0
0
∗

∗
0
∗
0
0
0

0
∗
0
0
0
0

∗
0
∗
0
0
0

0
0
0
∗
0
0

0
0
0
0
∗
∗

0
0
0
0
∗
∗














.




Figure 5: An illustration of the sparsity of the matrices [Bi−1 ]Bi . A label of an element
b ∈ Bi−1 is connected with a label of an element b0 ∈ Bi if and only if they are related.

5

Connection with the Robinson-Schensted insertion
algorithm

In Figure 5 the vertical order of the labels of the elements of each basis Bi has been
carefully chosen in order to simplify the figure. In fact, the order is such that each horizontal line corresponds to a well known process: the Robinson-Schensted (RS) insertion
algorithm (see [10]).
Observe that each horizontal line gives the sequence –reading from left to right– that
is obtained by applying the RS insertion algorithm to a word corresponding to an element
of the basis B0 , which is a word in the alphabet {1, 2}. The elements of this sequence are
11

triples (P, Q, ω) where P is a semistandard tableau, Q is a standard tableau and ω is a
word in the alphabet {1, 2}. In our situation P is filled with letters in {1, 2} so its height
is at most 2. It turns out that the triple (P, Q, ω) is determined by the pair (Q, ω) so P
can be ommited.
Definition 2. Let b ∈ Bi−1 and b0 ∈ Bi . We say that b and b0 are RS-related if the label
of b0 is obtained by applying the RS insertion step to the label of b.
From the definitions it is immediate the following (see Figure 5 for an illustration).
Theorem 3. If b ∈ Bi−1 and b0 ∈ Bi are RS-related then they are related.

6

Application to the computation of isotypic components

The upper bound we obtained for the algebraic complexity of the Fourier transform can
be applied to the problem of computing the isotypic projections of a given function on
the Johnson graph.
For a = 0, ..., s, let Fa be the isotypic component of F corresponding to the Young
diagram (n−a, a) under the action of the group Sn . Since these components are orthogonal
and expand the space F, given a function f ∈ F there are uniquely determined functions
fa ∈ Fa such that
s
X
f=
fa
a=0

For H ⊆ {0, ..., s} let fH be defined by
fH =

X

fa

a∈H

Theorem 4. Assume that the matrices [Bi−1 ]Bi for i = 2, 3, ..., n have been computed.
Given a column vector
 [f ]B0 with f ∈ F, the column vector [fH ]B0 can be computed using
at most 4(n − 1) nk operations.
Proof. First we apply the Fourier transform
to the function f , so that we obtain the

n
column vector [f ]Bn using 2(n − 1) k operations. The basis Bn is parametrized by all
Young tableaux of shape (n − a, a) for a = 0, ..., s. Then we substitute by 0 the values of
the entries of the vector [f ]Bn that correspond to Young tableaux of shape (n − a, a) with
a not in H. The resulting column vector is [fH ]Bn . Finally we apply the inverse Fourier
transform to [fH ]Bn so that we obtain [fH ]B0 using 2(n − 1) nk more operations.
Theorem 5. Assume that the matrices [Bi−1 ]Bi for i = 2, 3, ..., n have been computed.
Given a column vector [f ]B0 with f ∈ F, all the weights kfa k2 , for a = 0, ..., s, can be
computed using at most (2n − 1) nk operations.
Proof. Observe that kfa k2 = k[fa ]Bn k2 . To obtain the column vector [fa ]Bn , we apply
the Fourier transform to the function f , so that we obtain the column vector [f ]Bn using
2(n − 1) nk operations. Then we select the entries of the vector [f ]Bn that correspond to
Young tableaux of shape (n−a, a), and we compute the sum of the squares
 of these entries.
Doing this for all the values of a can be accomplished using at most nk operations.
12

7

Further directions

Our results shows that once the matrices [Bi ]Bi−1 have been computed
for i = 2, 3, ..., n,

n
the Fourier transform of any vector f can be computed in O(n k ) operations. It emerges
the problem of computing efficiently these matrices, that is, finding
 an algorithm that
on input (n, k) it computes all the matrices [Bi ]Bi−1 using O(nc nk ) operations for some
constant c. We conjecture that such an algorithm exists.

References
[1] Arora, Sanjeev, and Boaz Barak. Computational complexity: a modern approach.
Cambridge University Press, (2009).
[2] Babai, László. Graph Isomorphism in Quasipolynomial Time. arXiv:1512.03547v2
(2016):1-89
[3] Bürgisser, Peter, Michael Clausen, and Mohammad A. Shokrollahi. Algebraic complexity theory. Vol. 315. Springer Science and Business Media, (2013).
[4] Cooley, James W. and Tukey, John W. An Algorithm for the Machine Calculation
of Complex Fourier Series. IBM Watson Research Center (1964): 297-301.
[5] Delsarte, Philippe, and Vladimir I. Levenshtein Association schemes and coding theory. IEEE Transactions on Information Theory 44.6 (1998): 2477-2504.
[6] Diaconis, Persi W. A generalization of spectral analysis with application to ranked
data. The Annals of Statistics (1989): 949-979.
[7] Diaconis, Persi W. Group representations in probability and statistics. Lecture NotesMonograph Series (1988): i-192.
[8] Diaconis, Persi W. and Daniel Rockmore. Efficient computation of isotypic projections for the symmetric group. DIMACS Ser. Discrete Math. Theoret. Comput. Sci
11 (1993): 87-104.
[9] Driscoll, James R., Healy, Dennis M. Jr, and Rockmore, Daniel N. Fast discrete polynomial transforms with applications to data analysis for distance transitive graphs.
SIAM Journal on Computing 26.4 (1997): 1066-1099.
[10] Fulton, William. Young tableaux: with applications to representation theory and geometry. Vol. 35. Cambridge University Press, 1997.
[11] Fulton, William and Harris Joe. Representation theory. Vol. 129. Springer Science
and Business Media, 1991.
[12] Maslen, David K., Orrison, Michael E. and Rockmore, Daniel N. Computing isotypic projections with the Lanczos iteration. SIAM Journal on Matrix Analysis and
Applications 25.3 (2003): 784-803.

13

[13] Papadimitriou, Christos H. Computational complexity. John Wiley and Sons Ltd.,
(2003).
[14] Stanton, Dennis. Orthogonal polynomials and Chevalley groups. Special Functions:
group theoretical aspects and applications. Springer Netherlands, 1984. 87-128.
[15] Arvind, V.; Torán, Jacobo, Isomorphism testing: Perspectives and open problems,
Bulletin of the European Association for Theoretical Computer Science, 86 (2005):
66?84.
[16] Vershik, Andrei. M. and Okounkov Anatoly. Yu. A New Approach to Representation
Theory of the Symmetric Groups. ESI The Erwin Schödinger International Institute
for Mathematical Physics (1996): 1-21.

14

