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
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
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
