EngageS

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.

Members

You can find the members of the project on our member page .

Publications

A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler-Leman Dimension.

Jendrik Brachter, Pascal Schweitzer.
ESA 2022. ArXiv

SAT Preprocessors and Symmetry.

Markus Anders.
SAT 2022. ArXiv DOI
Award for Best Student Paper

Choiceless Polynomial Time with Witnessed Symmetric Choice.

Moritz Lichter, Pascal Schweitzer.
LICS 2022. ArXiv DOI

A Characterization of Individualization-Refinement Trees.

Markus Anders, Jendrik Brachter, Pascal Schweitzer.
ISAAC 2021. ArXiv DOI

Limitations of the Invertible-Map Equivalences.

Anuj Dawar, Erich Grädel, Moritz Lichter.
To appear in the Journal of Logic and Computation. ArXiv

Parallel Computation of Combinatorial Symmetries.

Markus Anders, Pascal Schweitzer.
ESA 2021. ArXiv DOI

Comparative Design-Choice Analysis of Color Refinement Algorithms Beyond the Worst Case.

Markus Anders, Pascal Schweitzer, Florian Wetzels.
ICALP 2021. ArXiv DOI

Search Problems in Trees with Symmetries: near optimal traversal strategies for individualization-refinement algorithms.

Markus Anders, Pascal Schweitzer.
ICALP 2021. ArXiv DOI

Separating Rank Logic from Polynomial Time.

Moritz Lichter.
LICS 2021. ArXiv DOI
Kleene Award for Best Student Paper

Resolution with Symmetry Rule applied to Linear Equations.

Pascal Schweitzer, Constantin Seebach.
STACS2021. ArXiv DOI

Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time.

Moritz Lichter, Pascal Schweitzer.
CSL 2021. ArXiv DOI

Engineering a Fast Probabilistic Isomorphism Test.

Markus Anders, Pascal Schweitzer.
ALENEX 2021. ArXiv DOI

Deep Weisfeiler Leman.

Martin Grohe, Pascal Schweitzer, Daniel Wiebking.
SODA 2021. ArXiv DOI

2.5-Connectivity: Unique Components, Critical Graphs, and Applications.

Irene Heinrich, Till Heller, Eva Schmidt, Manuel Streicher.
WG 2020. ArXiv DOI

On the Weisfeiler-Leman Dimension of Finite Groups.

Jendrik Brachter, Pascal Schweitzer.
LICS 2020. ArXiv DOI

Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm.

Moritz Lichter, Ilia Ponomarenko, Pascal Schweitzer.
LICS 2019. ArXiv DOI

A unifying method for the design of algorithms canonizing combinatorial objects.

Pascal Schweitzer, Daniel Wiebking.
STOC 2019. ArXiv DOI

Tools

As part of the project, the following tools concerning practical symmetry detection and exploitation were developed:

dejavu : probabilistic, parallel graph automorphism and isomorphism solver
sassy: preprocessor for symmetry detection

All the above tools are freely available and open source.