About me.
Hi, I’m Markus. I’m passionate about exploring new ideas in computer science – and sharing that passion through teaching. 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 with 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 intuitively exploit symmetry by, for example,
invoking “without loss of generality” arguments.
Looking at the equation x^2 + 2xy + y^2, we can see that x and y play symmetric roles,
and shorten our discussion accordingly.
Algorithms cannot intuitively do so on their own; we need to carefully design them to exploit symmetry.
Two complementary research interests of mine are algorithms to detect symmetry and algorithms to exploit symmetry. In both cases, I study practical algorithms and mathematical insights into these practical algorithms. Symmetry detection is closely related to the graph isomorphism problem, and has natural ties to algorithmic group theory. Symmetry exploitation, on the other hand, involves adapting existing algorithms, such as in Boolean satisfiability or mixed-integer programming.
Concretely, together with Pascal Schweitzer, I developed dejavu, the fastest tool for combinatorial symmetry detection, based on several new theoretical insights.
With Sofia Brenner and Gaurav Rattan, I developed satsuma, an algorithm that exploits symmetry in the Boolean satisfiability problem,
which successfully speeds up the fastest SAT solvers.
Research software.
My research involves designing and investigating the limits of practical algorithms. All my 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 want them to be easy-to-use in practice. Hence, I’m always happy to get 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.
- “Orbitopal Fixing in SAT”
Markus Anders, Cayden Codel, Marijn J. H. Heule
TACAS 2026 🏆 ETAPS distinguished paper pdf - “Faster Certified Symmetry Breaking Using Orders with Auxiliary Variables”
Markus Anders, Bart Bogaerts, Benjamin Bogø, Arthur Gontier, Wietze Koops, Ciaran McCreesh, Magnus O. Myreen, Jakob Nordström, Andy Oertel, Adrian Rebola-Pardo, Yong Kiam Tan
AAAI 2026 pdf - “Satsuma: Structure-based Symmetry Breaking in SAT” – full version of [13]
Markus Anders, Sofia Brenner, Gaurav Rattan
JAIR Vol. 85, 2026 pdf - “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” at RPTU Kaiserslautern-Landau, 2026
- “Algorithm Engineering (Seminar)” at RPTU Kaiserslautern-Landau, 2025/2026
- “Algorithms and Satisfiability” at RPTU Kaiserslautern-Landau, 2025/2026
- “Algorithms and Datastructures” 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.