Publications of Manuel Bodirsky

Links

• FIS-Export of the chair

• Free access to Preprints and postprints via ArXiv

• My publications in zbMATHOpen (good coverage in mathematics; free access). 
• My publications in MathSciNet (good coverage in mathematics; login required): MathSciNet database.
• My publications in DBLP (good coverage in computer science): DBLP database
• My publications in the research information system of TU Dresden: FIS. 
• Google Scholar
• My publication list at Ecole Polytechnique; no longer maintained. 

Publications since 2014

• Homogeneous structures, their reducts and automorphism groups
• Infinite-domain constraint satisfaction and finite model theory
• Oligomorphic clones and complexity of constraint satisfaction
• Valued CSPs
• Relation Algebras and the Network Satisfaction Problem
• Primitive positive constructability on finite structures
• Numeric CSP's
• Misc

1. Homogeneous structures, their reducts and automorphism groups

• A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory, 2024, TOCT, with Bertalan Bodor
• Solving equation systems in ω -categorical algebras, 2021, JML, with Thomas Quinn-Gregson
• Datalog-Expressibility for Monadic and Guarded Second-Order Logic, 2021, LZI, with Simon Knäuer, Sebastian Rudolph
• Canonical functions: A proof via topological dynamics, 2021, CDM, with Michael Pinsker
• The Complexity of Combinations of Qualitative Constraint Satisfaction Problems, 2020, LMCS, with Johannes Greiner
• The universal homogeneous binary tree, 2018, J. Log. Comput., with David Bradley-Williams, Michael Pinsker, András Pongrácz
• The Reducts of the homogeneous Binary Branching C-Relation, 2016,J. Symb. Log., with Peter Jonsson, Trung Van Pham
• Reducts of Structures and Maximal-Closed Permutation Groups, 2016, J. Symb. Log., with Dugald Macpherson
• New Ramsey Classes from Old, 2014, Electron. J. Comb.

Related Coursenotes: Automorphism groups, Model Theory

Back to the top

2. Infinite-domain constraint satisfaction and finite model theory

• Hereditary First-Order Model Checking, 2024, with Santiago Guzmán Pro

• On the Descriptive Complexity of Temporal Constraint Satisfaction Problems, 2023, JACM, with Jakub Rydval

• Forbidden Tournaments and the Orientation Completion Problem, 2023, SIDMA, with Santiago Guzmán Pro

• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP, 2021, SICOMP, with Florent Madelaine, Antoine Mottet

• Datalog-Expressibility for Monadic and Guarded Second-Order Logic, 2021, LZI, with Simon Knäuer, Sebastian Rudolph

• ASNP: A Tame Fragment of Existential Second-Order Logic, 2020, CiE, with Simon Knäuer, Florian Starke

Book: Complexity of Infinite-Domain Constraint Satisfaction

Back to the top

3. Oligomorphic clones and complexity of constraint satisfaction

• A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory, 2024, TOCT, with Bertalan Bodor

• Complexity Classification Transfer for CSPs via Algebraic Products, 2024, SICOMP, with Peter Johnsson, Barnaby Martin, Antoine Mottet, Žaneta Semanišinová

• On the Descriptive Complexity of Temporal Constraint Satisfaction Problems, 2023, JACM, with Jakub Rydval

• Network Satisfaction Problems Solved by k-Consistency, 2023, ICALP 2023, with Simon Knäuer

• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom, 2022, JAIR, with Simon Knäuer

• Canonical functions: a proof via topological dynamics, 2021, CDM, with Michael Pinsker

• Solving equation systems in ω -categorical algebras, 2021, JML, with Thomas Quinn-Gregson

• Projective clone Homomorphisms, 2021, J. Symb. Log., with Michael Pinsker, András Pongrácz

• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP, 2021, SICOMP, with Florent Madelaine, Antoine Mottet

• Tractable Combinations of Temporal CSPs, 2020, LMCS with Johannes Greiner, Jakub Rydval

• The Complexity of Combinations of Qualitative Constraint Satisfaction Problems, 2020, LMCS, with Johannes Greiner

• Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems), 2019, IEEE, with Antoine Mottet, Miroslav Olsak, Jakub Oprsal, Michael Pinsker, Ross Willard

• Constraint Satisfaction Problems for Reducts of Homogeneous Graphs, 2019, SICOMP, with Barnaby Martin, Michael Pinsker, András Pongrácz

• A Dichotomy for First-Order Reducts of Unary Structures, 2018, LMCS, with Antoine Mottet

• The Complexity of Phylogeny Constraint Satisfaction Problems, 2017, ACM TOCL, with Peter Johnsson, Trung Van Pham

• Schaefer's Theorem for Graphs, 2015, JACM , with Michael Pinsker

Book: Complexity of Infinite-Domain Constraint Satisfaction

Back to the top

4. Valued CSPs

• Temporal Valued Constraint Satisfaction Problems, 2024, MFCS, with Žaneta Semanišinová, Édouard Bonnet

• The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems, 2023, LICS, with Žaneta Semanišinová, Carsten Lutz

• Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation, 2022, ACM TOCL, with Marcello Mamino, Caterina Viola

Back to the top

5. Relation Algebras and the Network Satisfaction Problem

• Network Satisfaction Problems Solved by k-Consistency, 2023, ICALP 2023, with Simon Knäuer
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom, 2022, JAIR, with Simon Knäuer

• Hardness of Network Satisfaction for Relation Algebras with Normal Representations, 2020, RAMiCS, with Simon Knäuer

• Finite Relation Algebras with Normal Representations, 2018, RAMiCS 2018

• A Model-Theoretic View on Qualitative Constraint Reasoning, 2017, JAIR, with Peter Jonsson

Book: Complexity of Infinite-Domain Constraint Satisfaction

Back to the top

6. Primitive positive constructability on finite structures

• SLAM Datalog, 2024, ICDT 2025, with Florian Starke

• The lattice of clones of self-dual operations collapsed, 2023, IJAC, with Albert Vucaj, Dmitriy Zhuk

• The smallest hard trees, 2022, Constraints, with Jakub Bulín, Florian Starke, Michael Wernthaler

• Maximal Digraphs with Respect to Primitive Positive Constructability, 2022, Combinatorica, with Florian Starke

• Smooth digraphs modulo primitive positive constructability and cyclic loop conditions, 2021, IJAC, with Florian Starke, Albert Vucaj

Related coursenotes:  Graph Homomorphisms and Universal Algebra

Back to the top

7. Numeric CSP's

• Reducing Stochastic Games to Semidefinite Programming, 2025, ICALP 2025 with Georg Loho, Mateusz Skomra

• Spectrahedral Shadows and Completely Positive Maps on Real Closed Fields, 2022, JEMS, with Mario Kummer, Andreas Thom

• Discrete Temporal Constraint Satisfaction Problems, 2018, JACM, with Antoine Mottet, Barnaby Martin

• Tropically Convex Constraint Satisfaction, 2018, Theory Comput. Syst., with Marcello Mamino

• The Complexity of Disjunctive Linear Diophantine Constraints, 2018, MFCS, with Barnaby Martin, Marcello Mamino, Antoine Mottet

• Constraint Satisfaction Problems over Numeric Domains, 2017, in The Constraint Satisfaction Problem: Complexity and Approximability, with Marcello Mamino

Back to the top

8. Misc

• Model-checking positive equality free logic on a fixed structure (direttissima), 2024, with Marcin Kozik, Florent Madelaine, Barnaby Martin, Michal Wrona

• Universal Horn Sentences and the Joint Embedding Property, 2022, DMTCS, with Jakub Rydval, André Schrottenloher

• On Logics and Homomorphism Closure, 2021, LICS 2021, with Thomas Feller, Simon Knäuer, Sebastian Rudolph

• Tractability of quantified temporal constraints to the max, 2014, IJAC, with Hubie Chen, Michał Wrona

• A Notation System for Tango, 2004. Updated 2025.

Back to the top