Practically efficient algorithms for coherent configurations

Datum

23.06.2017

Zeit

13:15 - 14:15

Sprecher

Dr. Sven Reichard

Zugehörigkeit

TU Dresden, Institut für Algebra

Sprache

en

Hauptthema

Mathematik

Andere Themen

Mathematik

Host

Dr. E. Lehtonen

Beschreibung

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

Letztmalig verändert: 23.06.2017, 12:12:03