Manuel Bodirskys Publikationen

Links

• FIS-Export des Lehrstuhls
• Freier Zugang zu Preprints and Postprints via ArXiv
• Meine Publikationen in  zbMATHOpen (gute Abdeckung in Mathematik; freier Zugang).
• Meine Publikationen in DBLP (gute Abdeckung in Informatik). 
• Meine Publikationen auf Orcid.
• Meine Publikationen in MathSciNet (gute Abdeckung in Mathematik; Login notwendig). 
• Meine Publikationen im Forschungsinformationssystem (FIS) der TU Dresden. 
• Google Scholar.
• Meine Publikationsliste an der Ecole Polytechnique; wird nicht weiter aktualisiert.

Publikationen ab 2014

• Automorphismengruppen und Redukte homogener Strukturen
• Constraint Satisfaction Probleme über unendlichen Bereichen und endliche Modelltheorie
• Oligomorphe Klone und die Komplexität von Constraint Satisfaction Problemen
• Bewertete Constraint Satisfaction Probleme
• Relationsalgebren und das NSP
• Primitiv positive Konstruierbarkeit auf endlichen Strukturen
• Numerische CSPs
• Misc

1. Automorphismengruppen und Redukte homogener Strukturen

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

Vorlesungsskripte: Automorphism groups, Model Theory

Zurück zur Übersicht

2. Constraint Satisfaction Probleme über unendlichen Bereichen und endliche Modelltheorie

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

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

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

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

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

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

Buch: Complexity of Infinite-Domain Constraint Satisfaction

Zurück zur Übersicht

3. Oligomorphe Klone und die Komplexität von Constraint Satisfaction Problemen

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Buch: Complexity of Infinite-Domain Constraint Satisfaction

Zurück zur Übersicht

4. Bewertete Constraint Satisfaction Probleme

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

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

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

Zurück zur Übersicht

5. Relationsalgebren und das NSP

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

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

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

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

Buch: Complexity of Infinite-Domain Constraint Satisfaction

Zurück zur Übersicht

6. Primitiv positive Konstruierbarkeit auf endlichen Strukturen

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

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

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

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

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

Vorlesungsskript: Graph Homomorphisms and Universal Algebra

Zurück zur Übersicht

7. Numerische CSPs

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

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

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

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

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

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

Zurück zur Übersicht

8. Misc

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

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

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

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

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

Zurück zur Übersicht