EngageS

Next Generation Algorithms for Grabbing and Exploiting Symmetry

Symmetry is a ubiquitous concept that appears in virtually all areas of computer science. Algorithmic symmetry detection and exploitation is the concept of finding intrinsic symmetries of a given object and then using these symmetries to our advantage. Application areas range from convolutional neural networks in machine learning to computer graphics, chemical data bases and beyond. The ERC-funded Project EngageS studies the algorithmic problem of detecting and exploiting symmetry both from a theoretical as well as from a practical standpoint. A major goal is to bring theory and practice closer together. This is for example done by modeling and formalizing specific algorithmic aspects regarding symmetry, developing theoretically optimal solutions, and transferring these back into practice.

On the theory side, symmetry detection is often referred to as the graph isomorphism problem. This problem has unknown complexity status and remains one of the most famous open problems in theoretical computer science. In the project we investigate various aspects of the problem and use a diverse portfolio of techniques to explore the limits of symmetry exploitation. These include computational group theory, design theory, algebraic graph theory, logics, as well as various techniques for algorithm analysis. We also investigate related algorithmic problems such as canonization, computing normal forms and generation tasks.

Publications

M. Lichter
Separating Rank Logic from Polynomial Time.

To appear at LICS2021
Kleene Award for Best Student Paper
[arXiv]

P. Schweitzer, C. Seebach
Resolution with Symmetry Rule applied to Linear Equations

2021 Proceedings of the Symposium on Theoretical Aspects of Computer Science. STACS2021
[arXiv]

M. Lichter, P. Schweitzer,
Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time.

Proceedings of the 29th EACSL Annual Conference on Computer Science Logic. CSL2021
(DOI) [arXiv]

M. Anders, P. Schweitzer,
Engineering a Fast Probabilistic Isomorphism Test.

2021 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX2021
[arXiv]

M. Grohe, P. Schweitzer, D. Wiebking
Deep Weisfeiler Leman.

Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms. SODA2021
[arXiv]

I. Heinrich, T. Heller, E. Schmidt, M. Streicher
2.5-Connectivity: Unique Components, Critical Graphs, and Applications.

Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science. WG2020
[arXiv]

J. Brachter, P. Schweitzer
On the Weisfeiler-Leman Dimension of Finite Groups.

35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020. LICS2020
(DOI) [arXiv]

M. Lichter, I. Ponomarenko, P. Schweitzer
Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm.
34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS2019, Vancouver, BC, Canada, June 24-27, 2019
(DOI) [arXiv]

P. Schweitzer, D. Wiebking
A unifying method for the design of algorithms canonizing combinatorial objects.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC2019, Phoenix, AZ, USA, June 23-26, 2019
(DOI) [arXiv]

---