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
The Complexity of Symmetry Breaking Beyond Lex-Leader.
Markus Anders, Sofia Brenner, and Gaurav Rattan.
CP 2024. DOI
Computing edge colored ultrahomogeneous graphs.
Irene Heinrich, Eda Kaja, Pascal Schweitzer.
DMD 2024. Paper (opens in new tab)
The flexibility among 3-decompositions.
Irene Heinrich, Lena Volk
DMD 2024. Paper (opens in new tab)
Finite Vertex-colored Ultrahomogeneous Oriented Graphs.
Irene Heinrich, Eda Kaja, Pascal Schweitzer.
WG 2024. ArXiv
On the modular isomorphism problem for groups with center of index at most p3.
Sofia Brenner, Diego Garcı́a-Lucas
Archiv der Mathematik, 2024. DOI
Tuple regularity and k-ultrahomogeneity for finite groups.
Sofia Brenner.
Journal of Group Theory, 2024. DOI
Satsuma: Structure-Based Symmetry Breaking in SAT.
Markus Anders, Sofia Brenner, and Gaurav Rattan.
SAT 2024. DOI
Non-Pool-Based Line Planning on Graphs of Bounded Treewidth.
Irene Heinrich, Philine Schiewe, Constantin Seebach.
ATMOS 2023. DOI
Using Light Spanning Graphs for Passenger Assignment in Public Transport.
Irene Heinrich, Olli Herrala, Philine Schiewe, Topias Terho.
ATMOS 2023. DOI
Reductions for the 3-Decomposition Conjecture.
Oliver Bachtler, Irene Heinrich.
LAGOS 2023. DOI
Exploration of Graphs with Excluded Minors.
Júlia Baligács, Yann Disser, Irene Heinrich, Pascal Schweitzer.
ESA 2023. DOI
Countable ultrahomogeneous 2-colored graphs consisting of disjoint unions of cliques.
Sofia Brenner, Irene Heinrich.
EUROCOMB 2023. DOI
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
