About me.
Hi, I’m Markus. I’m passionate about exploring new ideas in computer science – and sharing that passion through teaching. Currently, I’m a substitute professor (W2) for theoretical computer science at RPTU Kaiserslautern-Landau (2025-present). Previously, I was a postdoctoral researcher at KU Leuven in the group of Bart Bogaerts (2024-2025). I did my PhD with Pascal Schweitzer at TU Darmstadt (2019 - 2024).
My research interests, broadly.
- combinatorial symmetry detection and exploitation
- graph algorithms
- permutation group algorithms
- Boolean satisfiability
- certifying algorithms
- algorithm engineering
Symmetry in Practice.
Symmetry is everywhere.
In mathematics, we often intrinsically make use of symmetry by, for example,
invoking “without loss of generality” arguments.
Looking at the equation x^2 + 2xy + y^2, we can immediately see that x and y are symmetrical, and shorten our discussion accordingly.
Algorithms can not intrinsically do so on their own; we have to design them to use symmetry.
One important research interest of mine is the design and analysis of algorithms for symmetry detection and symmetry exploitation. In particular, I focus on practical algorithms and mathematical insights into these practical algorithms. Symmetry detection is strongly related to the graph isomorphism problem, and has natural ties to algorithmic group theory. Symmetry exploitation involves adapting existing algorithms in various fields, such as in Boolean satisfiability or constraint programming.
Concretely, together with Pascal Schweitzer, based on several new theoretical insights, I made the currently fastest tool for combinatorial symmetry detection
called dejavu.
Furthermore, together with Sofia Brenner and Gaurav Rattan, I made an algorithm exploiting symmetry in the Boolean satisfiability problem (SAT) called satsuma,
which sucessfully speeds up the fastest known SAT algorithms.
Research software.
A crucial part of my research involves designing and investigating the limits of practical algorithms. All these algorithms are available as open source software with liberal licensing. I try to take care of these tools as much as I can, and I strive for them to be easy to use in practice. Hence, I’m always happy to receive feedback if you happen to try them out.
- dejavu (2019-present)
state-of-the-art solver and library for the detection and manipulation of symmetry
used in SCIP
- satsuma (2024-present)
state-of-the-art symmetry breaking for Boolean satisfiability testing
🏆 certified tracks of PB Competition 2025
with RoundingSat
- sassy (2023)
preprocessor for symmetry detection, now subsumed into dejavu
I have also in some way contributed to the development of the following software:
- VeriPB (2025)
proof-checker for VeriPB proofs
Peer-reviewed Publications.
- “Satsuma: Structure-based Symmetry Breaking in SAT” – full version of [13]
Markus Anders, Sofia Brenner, Gaurav Rattan
Accepted by the Journal of Artificial Intelligence Research (JAIR) - “Efficient Algorithms for Symmetry Detection”
Markus Anders
PhD Thesis pdf - “The Complexity of Symmetry Breaking Beyond Lex-Leader”
Markus Anders, Sofia Brenner, Gaurav Rattan
CP 2024 pdf - “Satsuma: Structure-based Symmetry Breaking in SAT”
Markus Anders, Sofia Brenner, Gaurav Rattan
SAT 2024 pdf - “Algorithms Transcending the SAT-Symmetry Interface”
Markus Anders, Pascal Schweitzer, Mate Soos
SAT 2023 pdf - “Engineering a Preprocessor for Symmetry Detection”
Markus Anders, Pascal Schweitzer, Julian Stieß
SEA 2023 pdf - “Taming Horizontal Instability in Merge Trees: On the Computation of a Comprehensive Deformation-based Edit Distance”
Florian Wetzels, Markus Anders, Christoph Garth
TopoInVis 2023 pdf - “A Systematic Approach to Universal Random Features in Graph Neural Networks”
Billy Joe Franks, Markus Anders, Marius Kloft, Pascal Schweitzer
TMLR 2023 pdf - “SAT Preprocessors and Symmetry”
Markus Anders
SAT 2022 🏆 best student paper award pdf - “A Characterization of Individualization-Refinement Trees”
Markus Anders, Jendrik Brachter, Pascal Schweitzer
ISAAC 2021 pdf - “Parallel Computation of Combinatorial Symmetries”
Markus Anders, Pascal Schweitzer
ESA 2021 pdf - “Search Problems in Trees with Symmetries: Near Optimal Traversal Strategies for Individualization-Refinement Algorithms”
Markus Anders, Pascal Schweitzer
ICALP 2021 pdf - “Comparative Design-Choice Analysis of Color Refinement Algorithms Beyond the Worst Case”
Markus Anders, Pascal Schweitzer, Florian Wetzels
ICALP 2021 pdf - “Engineering a Fast Probabilistic Isomorphism Test”
Markus Anders, Pascal Schweitzer
ALENEX 2021 pdf - “A Formal Semantics of Exposed Datapath Architectures with Buffered Processing Units”
Markus Anders, Klaus Schneider
ACSD 2019 pdf - “On Memory Optimal Code Generation for Exposed Datapath Architectures with Buffered Processing Units”
Markus Anders, Anoop Bhagyanath, Klaus Schneider
ACSD 2018 pdf
Other Publications.
- “Documentation of VeriPB and CakePB for the SAT Competition 2025”
Markus Anders, Bart Bogaerts, Benjamin Bogø, Arthur Gontier, Wietze Koops, Ciaran McCreesh, Magnus O. Myreen, Jakob Nordström, Adrian Rebola-Pardo, Andy Oertel, and Yong Kiam Tan
SAT Competition 2025 pdf
Teaching.
As lecturer:
- “Algorithms and Datastructures” (8 ECTS) at RPTU Kaiserslautern-Landau, 2025
As assistant:
- As a PhD, I assisted in the courses “Complexity Theory” (TUK), “Algorithms and Datastructures” (TUK), “Algorithms and Symmetry” (TUK), “Automata Theory and Formal Languages” (TUD), and “Propositional and First-order Logics” (TUD).
As student assistant:
- As a student teaching assistant, I conducted exercise sessions for “Algorithmic Group Theory”, “Computer Systems”, and “Design and Analysis of Algorithms” at TU Kaiserslautern.