<p>One application that I know of is the connection between <a href="http://en.wikipedia.org/wiki/Combinatorial_design" rel="nofollow">combinatorial designs</a> (which are related to associative schemes) and coding theory. Delsarte's program in particular has lead to some interesting LP based bounds for codes. I don't know much about these but I remember that <a href="http://www.cs.huji.ac.il/~salex/" rel="nofollow">Alex Samorodnitsky</a> has worked on these connections (for example, <a href="http://www.cs.huji.ac.il/~salex/papers/delsarte_cover.pdf" rel="nofollow">this</a>, <a href="http://www.cs.huji.ac.il/~salex/papers/kl.ps" rel="nofollow">this</a>, <a href="http://www.cs.huji.ac.il/~salex/papers/dels_ft.ps" rel="nofollow">this</a> and <a href="http://www.cs.huji.ac.il/~salex/papers/dels_lin.ps" rel="nofollow">this</a>). Perhaps some expert can shed more light on this. </p>

CC BY-SA 2.5
2010-11-17T19:44:43.870Z
2010-11-17T22:05:12.017Z
2010-11-17T22:05:12.017Z
Ramprasad
<p>Coherent configurations are a close generalization of association schemes they have been used in Graph Isomorphism and Matrix Multiplication. (See e.g. <a href="https://cameroncounts.wordpress.com/2014/06/08/terminology-association-scheme-or-coherent-configuration/" rel="nofollow noreferrer">this blog post of Peter Cameron that discusses the differences</a> - in particular in a CC the diagonal can be a union of classes instead of just one class as in an AS, and the relations need not be symmetric. But the key condition (3) from the OQ is the same.)</p>
<p>They were introduced independently by Higman to study permutation groups and by Weisfeiler &amp; Leman specifically for the purpose of their GI algorithm. And they continue to play an important role in GI today, including in Babai's quasi-polynomial-time algorithm (<a href="https://doi.org/10.1145/2897518.2897542" rel="nofollow noreferrer">STOC '16</a>).</p>
<p>Cohn &amp; Umans (<a href="https://doi.org/10.1137/1.9781611973105.77" rel="nofollow noreferrer">SODA '13</a>, <a href="https://arxiv.org/abs/1207.6528" rel="nofollow noreferrer">arXiv</a>) also proposed a way to use coherent configurations to develop better algorithms for matrix multiplication, generalizing their 2003 group-theoretic approach.</p>

CC BY-SA 4.0
2022-05-02T18:47:10.220Z
2022-05-02T18:47:10.220Z
Joshua Grochow
<p>An <a href="https://en.wikipedia.org/wiki/Association_scheme" rel="nofollow noreferrer">association scheme</a> is defined as a pair <span class="math-container">$(V, R_0,R_1, \ldots,R_{n+1})$</span> of a set <span class="math-container">$V$</span> and relations <span class="math-container">$R_i$</span> on <span class="math-container">$V$</span> such that</p>
<ol>
<li><p><span class="math-container">$(x,y) \in R_i$</span> implies <span class="math-container">$(y,x) \in R_i$</span> for all <span class="math-container">$x, y \in V$</span>.</p>
</li>
<li><p><span class="math-container">$R_0 = \{ (x,x) \mid x \in V \}$</span></p>
</li>
<li><p>If <span class="math-container">$(x,y) \in R_k$</span>, the number of <span class="math-container">$z \in V$</span> such that <span class="math-container">$(x,z) \in R_i$</span> and <span class="math-container">$(y,z) \in R_j$</span> is a constant <span class="math-container">$c_{ijk}$</span> depending on <span class="math-container">$i$</span>, <span class="math-container">$j$</span> and <span class="math-container">$k$</span>, but not on the choice of <span class="math-container">$x$</span> or <span class="math-container">$y$</span>.</p>
</li>
</ol>
<p>An example of the application of the theory of association schemes to complexity theory is <a href="https://doi.org/10.1007/3-540-58691-1_58" rel="nofollow noreferrer">the following result of Evdomikov</a> from 1994:</p>
<blockquote>
<p>Under the Generalized Riemann Hypothesis, the irreducible factors of a degree <span class="math-container">$n$</span> polynomial over an explicitly given finite field of order <span class="math-container">$q$</span> can be found in time <span class="math-container">$(n^{\log n} \log q)^{O(1)}$</span>.</p>
</blockquote>
<p>So... question(s):</p>
<blockquote>
<p>Are there other, more recent applications of association schemes to complexity theory, or other TCS?</p>
<p>What is the current state of the art in factoring algorithms of polynomials over finite fields?</p>
</blockquote>
<p>Thanks in advance.</p>

CC BY-SA 2.5
2010-11-17T17:06:23.607Z
is there any helpful intuition about the reason such beasts are useful ?
Suresh Venkat
CC BY-SA 4.0
2022-05-02T18:48:56.273Z
@AaronSterling I know this is old, but it just came on my radar again. Maybe remove the "What's the state of the art in factoring of polynomials" since that seems like a totally separate question from the one in the title?
Joshua Grochow
CC BY-SA 4.0
2022-05-02T18:53:38.820Z
@SureshVenkat I don't know about intuition, but they show up naturally in a lot of places. I think of them as a generalization of groups (/group actions) that feels more like the combinatorics of a graph. For example, a strongly regular undirected graph is precisely an association scheme with $n=1$, where $R_1$ is the edges and $R_2$ is the non-edges. Cayley graphs, suitably interpreted, are also association schemes, as is the Cayley-Schrier graph of any (transitive) group action (for non-transitive you get a coherent configuration instead).
Joshua Grochow
<cc.complexity-theory><polynomials>
Applications of association schemes to complexity theory and other TCS
Aaron Sterling
# Applications of association schemes to complexity theory and other TCS

(Asked by: username_0 on 2010-11-17)

An [association scheme](https://en.wikipedia.org/wiki/Association_scheme) is defined as a pair $(V, R\_0,R\_1, \ldots,R\_{n+1})$ of a set $V$ and relations $R\_i$ on $V$ such that

1. $(x,y) \in R\_i$ implies $(y,x) \in R\_i$ for all $x, y \in V$.
2. $R\_0 = \{ (x,x) \mid x \in V \}$
3. If $(x,y) \in R\_k$, the number of $z \in V$ such that $(x,z) \in R\_i$ and $(y,z) \in R\_j$ is a constant $c\_{ijk}$ depending on $i$, $j$ and $k$, but not on the choice of $x$ or $y$.

An example of the application of the theory of association schemes to complexity theory is [the following result of Evdomikov](https://doi.org/10.1007/3-540-58691-1_58) from 1994:

> Under the Generalized Riemann Hypothesis, the irreducible factors of a degree $n$ polynomial over an explicitly given finite field of order $q$ can be found in time $(n^{\log n} \log q)^{O(1)}$.

So... question(s):

> Are there other, more recent applications of association schemes to complexity theory, or other TCS?
>
> What is the current state of the art in factoring algorithms of polynomials over finite fields?

Thanks in advance.

**Tags:** cc.complexity-theory, polynomials

> **Comments:**
> **username_1**: is there any helpful intuition about the reason such beasts are useful ?  
> **username_2**: @AaronSterling I know this is old, but it just came on my radar again. Maybe remove the "What's the state of the art in factoring of polynomials" since that seems like a totally separate question from the one in the title?  
> **username_2**: @SureshVenkat I don't know about intuition, but they show up naturally in a lot of places. I think of them as a generalization of groups (/group actions) that feels more like the combinatorics of a graph. For example, a strongly regular undirected graph is precisely an association scheme with $n=1$, where $R_1$ is the edges and $R_2$ is the non-edges. Cayley graphs, suitably interpreted, are also association schemes, as is the Cayley-Schrier graph of any (transitive) group action (for non-transitive you get a coherent configuration instead).  

---

## 2 answers

### Answer by username_3 on 2010-11-17. Score: 6

One application that I know of is the connection between [combinatorial designs](http://en.wikipedia.org/wiki/Combinatorial_design) (which are related to associative schemes) and coding theory. Delsarte's program in particular has lead to some interesting LP based bounds for codes. I don't know much about these but I remember that [Alex Samorodnitsky](http://www.cs.huji.ac.il/~salex/) has worked on these connections (for example, [this](http://www.cs.huji.ac.il/~salex/papers/delsarte_cover.pdf), [this](http://www.cs.huji.ac.il/~salex/papers/kl.ps), [this](http://www.cs.huji.ac.il/~salex/papers/dels_ft.ps) and [this](http://www.cs.huji.ac.il/~salex/papers/dels_lin.ps)). Perhaps some expert can shed more light on this.


---

### Answer by username_2 on 2022-05-02. Score: 2

Coherent configurations are a close generalization of association schemes they have been used in Graph Isomorphism and Matrix Multiplication. (See e.g. [this blog post of Peter Cameron that discusses the differences](https://cameroncounts.wordpress.com/2014/06/08/terminology-association-scheme-or-coherent-configuration/) - in particular in a CC the diagonal can be a union of classes instead of just one class as in an AS, and the relations need not be symmetric. But the key condition (3) from the OQ is the same.)

They were introduced independently by Higman to study permutation groups and by Weisfeiler & Leman specifically for the purpose of their GI algorithm. And they continue to play an important role in GI today, including in Babai's quasi-polynomial-time algorithm ([STOC '16](https://doi.org/10.1145/2897518.2897542)).

Cohn & Umans ([SODA '13](https://doi.org/10.1137/1.9781611973105.77), [arXiv](https://arxiv.org/abs/1207.6528)) also proposed a way to use coherent configurations to develop better algorithms for matrix multiplication, generalizing their 2003 group-theoretic approach.


---

