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.
A Characterization of Individualization-Refinement Trees.
Markus Anders, Jendrik Brachter, Pascal Schweitzer.
Limitations of the Invertible-Map Equivalences.
Anuj Dawar, Erich Grädel, Moritz Lichter.
Presented at Highlights of Logic 2021.