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?

Thanks in advance. I'll be offline for a day or two, I'm afraid. If there are issues with this question, I'll address them within 72 hours.

  • 3
    $\begingroup$ is there any helpful intuition about the reason such beasts are useful ? $\endgroup$ – Suresh Venkat Nov 17 '10 at 17:06

One application that I know of is the connection between combinatorial designs (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 has worked on these connections (for example, this, this, this and this). Perhaps some expert can shed more light on this.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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