Practically efficient algorithms for coherent configurations

Date

Jun 23, 2017

Time

1:15 PM - 2:15 PM

Speaker

Dr. Sven Reichard

Affiliation

TU Dresden, Institut für Algebra

Language

en

Main Topic

Mathematik

Other Topics

Mathematik

Host

Dr. E. Lehtonen

Description

In complexity theory we study the /theoretical/ complexity of algorithms, that is, the asymptotic behaviour of the amount of required resources (time, space, energy) as a function of the input size. For the practitioner who uses the algorithms it may be more interesting to know the /practical/ complexity, the resources required for specific instances of the problem on given hardware. Here, the size of the constants does matter. It turns out that in this case the simple model of computation with one processing unit and uniform memory access is not adequate. We look at two algorithmic problems related to coherent configurations, which are relational systems with a strong algebraic flavour. Weisfeiler-Leman (WL) stabilization computes the coarsest coherent refinement of a given configuration. It features in the recent improvements to the solution of the graph isomorphism problem. Its two-dimensional variant is of interest in algebraic graph theory. Two implementations were developed in the 1990's, with diverse theoretical and practical characteristics. We describe a few ways to outperform both classical implementations. S-rings are two-dimensional coherent configurations which admit a regular group of automorphisms. They play a role in the theory of Cayley graphs. The set of S-rings over a given group G is related to the set of two-closed overgroups of the regular action of G. Knowledge of their structure helps us solve the isomorphism problem for Cayley graphs over G. Enumeration of S-rings is hard, but it provides plenty of opportunity for efficient implementation.

Links

• Institut für Algebra: International Seminar

Last modified: Jun 23, 2017, 12:12:03 PM