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 .

Software libraries

As part of the project, the following free, open source tools for practical symmetry detection and exploitation on graphs were developed:

  • dejavu: fast probabilistic symmetry detection
  • sassy: preprocessor for symmetry detection

Publications

Twin-width of graphs with tree-structured decompositions.

Irene Heinrich, Simon Raßmann.
IPEC 2023. ArXiv


Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements.

Martin Grohe, Moritz Lichter, Daniel Neuen, Pascal Schweitzer.
FOCS 2023. ArXiv


Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting.

Moritz Lichter.
ICALP 2023. ArXiv DOI


Continuing the Quest for a Logic Capturing Polynomial Time – Potential, Limitations, and Interplay of Current Approaches.

Moritz Lichter.
PhD Thesis 2023.DOI More Information


Engineering a Preprocessor for Symmetry Detection.

Markus Anders, Pascal Schweitzer, Julian Stieß.
SEA 2023. ArXiv DOI


Algorithms Transcending the SAT-Symmetry Interface.

Markus Anders, Pascal Schweitzer, Mate Soos.
SAT 2023. ArXiv DOI


The Iteration Number of the Weisfeiler-Leman Algorithm.

Martin Grohe, Moritz Lichter, Daniel Neuen.
LICS 2023. ArXiv DOI


Automated testing and interactive construction of unavoidable sets for graph classes of small path-width.

Oliver Bachtler, Irene Heinrich.
Journal of Graph Theory, 2023. ArXiv DOI


Limitations of the invertible-map equivalences.

Anuj Dawar, Erich Grädel, Moritz Lichter.
Journal of Logic and Computation, 2023. ArXiv DOI

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

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.
Journal of the ACM, LICS 2021. ArXiv DOI (JACM)DOI (LICS)
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