EngageS: Next Generation Algorithms for Grabbing and Exploiting Symmetry

EngageS Logo

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.

ERC Logo Small

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.

Publications

ircharacterize

A Characterization of Individualization-Refinement Trees.

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

ArXiv

empty

Limitations of the Invertible-Map Equivalences.

Anuj Dawar, Erich Grädel, Moritz Lichter.

Presented at Highlights of Logic 2021.

ArXiv

parallelsym

Parallel Computation of Combinatorial Symmetries.

Markus Anders, Pascal Schweitzer.
ESA 2021.

ArXiv DOI

comparativedc3

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

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

ArXiv DOI

searchproblemlasvegas2

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

Markus Anders, Pascal Schweitzer.
ICALP 2021.

ArXiv DOI

Rank logic ML

Separating Rank Logic from Polynomial Time.

Moritz Lichter.
LICS 2021.

Kleene Award for Best Student Paper

ArXiv DOI

resolution_sym

Resolution with Symmetry Rule applied to Linear Equations.

Pascal Schweitzer, Constantin Seebach.
STACS2021.

ArXiv DOI

canon-dih-cc

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

Moritz Lichter, Pascal Schweitzer.
CSL 2021.

ArXiv DOI

engineering iso

Engineering a Fast Probabilistic Isomorphism Test.

Markus Anders, Pascal Schweitzer.
ALENEX 2021.

ArXiv DOI

deep_wl_rec

Deep Weisfeiler Leman.

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

ArXiv DOI

wg2020

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

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

ArXiv DOI

lics_rec

On the Weisfeiler-Leman Dimension of Finite Groups.

Jendrik Brachter, Pascal Schweitzer.
LICS 2020.

ArXiv DOI

algebraic_rec

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

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

ArXiv DOI

herd_fin_sets_rec

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

Pascal Schweitzer, Daniel Wiebking.
STOC 2019.

ArXiv DOI