# Applications of association schemes to complexity theory and other TCS

An 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 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?

• is there any helpful intuition about the reason such beasts are useful ? Nov 17, 2010 at 17:06
• @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? May 2 at 18:48
• @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). May 2 at 18:53