# Workshop on Association Schemes and Polynomial Factoring

Date: December 7 - 9, 2011

Venue: Room II.57, Friedrich-Ebert-Allee 144

**Wednesday, December 7th, 2011,**

**10:00-11:00** Paul-Hermann Zieschang (University of Texas): Hypergroups, Association Schemes, Buildings

Abstract: An association scheme is a complete graph with a coloring satisfying a certain regularity condition. Cayley graphs of groups are examples and show that each group can be viewed as an association scheme. - Buildings have been introduced by Jacques Tits in order to associate to each simple algebraic group over an arbitrary field a geometry in exactly the same way as the finite plane of order 2 (the Fano plane) is associated to the simple group L_3(2) of order 168. - In my talk I will first show that, in the theory of association schemes, the class of buildings plays exactly the same role which the class of the Coxeter groups plays in group theory. After that, I will show that the notion of a hypergroup is the concept which explains best the relationship between association schemes and buildings.

**11:30-12:30 **Sergei Evdokimov (Steklov Institute of Mathematics St. Petersburg): Factorization of polynomials over finite fields and odd association schemes

Abstract: To each separable split polynomial over a finite field we put in correspondence an odd association scheme on the set of its roots. Basing on this and the theory of multidimensional extensions of schemes a new deterministic algorithm to decompose a polynomial of degree n over a field of cardinality q into irreducible factors (a version of the author's quasipolynomial factorization algorithm) is constructed. Its running time (assuming GRH) is polynomial in n^{b_n} and log(q) where b_n is the maximum base number of a primitive odd association scheme on not more than n points.

**Thursday, December 8th, 2011**

**10:00-11:00 **Nitin Saxena (Bonn): Combinatorial Schemes in Algebraic Algorithms

Abstract: We introduce a new combinatorial object called m-scheme. It subsumes several standard objects like finite groups, strongly regular graphs and association schemes. An m-scheme on points V is basically a partition of V^m satisfying certain natural conditions. We state a conjecture about schemes and prove it in special cases. Finally, we show how it appears in the classical problem of factoring polynomials over finite fields.

This is joint work with Gabor Ivanyos and Marek Karpinski.

**11:30-12:30 **Manuel Arora (Bonn): Hanaki and Uno's Theorem for Schemes of Prime Order and its Application to Polynomial Factoring

Abstract: We give an overview of Hanaki and Uno's results for schemes of prime order. A central result of Hanaki and Uno states that all association schemes of prime order are commutative; moreover, all valencies of non-trivial relations and all multiplicities of non-trivial irreducible characters are constant for such schemes. We give an overview of the techniques used in the proof of Hanaki-Uno. Furthermore, we describe how their result for schemes of prime order can be applied in the context of polynomial factoring over finite fields, especially in connection with the new factoring algorithm by Ivanyos, Karpinski and Saxena. As we will show, the latter algorithm can factor prime-degree polynomials efficiently under certain conditions, as a direct result of Hanaki-Uno.

**Friday, December 9th, 2011**

**10:00-11:00 **Ilia Ponomarenko (Steklov Institute of Mathematics St. Petersburg): Polynomial-time recognizing of antisymmetric coherent configurations

Abstract: It is known that for any permutation group G of odd order one can find a subset of the permuted set whose stabilizer in G is trivial, and if G is primitive, then also a base of size at most 3. Both of these results are generalized to the coherentconfiguration of G (that is in this case a schurian antisymmetric coherent configuration).This enables us to construct a polynomial-time algorithm for recognizing and isomorphismtesting of schurian antisymmetric coherent configurations.

**11:30-12:30 **Sergei Evdokimov (Steklov Institute of Mathematics St. Petersburg): Schurity of S-rings and Cayley schemes

Abstract: Criteria for schurity and non-schurity of S-rings and Cayley schemes over an abelian (especially cyclic) group are given. In particular, we completely characterize those finite cyclic groups over which every S-ring, equivalently every Cayley scheme, is schurian (joint work with Istvan Kovacs and Ilia Ponomarenko).