Manuel Bodirsky

According to our database, Manuel Bodirsky authored at least 115 papers between 2001 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory.

Manuel Bodirsky, Bertalan Bodor

ACM Trans. Comput. Theory, 2024

Complexity Classification Transfer for CSPs via Algebraic Products.

Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet, Zaneta Semanisinová

SIAM J. Comput., 2024

Temporal Valued Constraint Satisfaction Problems.

Manuel Bodirsky, Édouard Bonnet, Zaneta Semanisinová

CoRR, 2024

Model-checking positive equality free logic on a fixed structure (direttissima).

Manuel Bodirsky, Marcin Kozik, Florent R. Madelaine, Barnaby Martin, Michal Wrona

CoRR, 2024

The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems.

Manuel Bodirsky, Zaneta Semanisinová, Carsten Lutz

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

2023

The lattice of clones of self-dual operations collapsed.

Manuel Bodirsky, Albert Vucaj, Dmitriy Zhuk

Int. J. Algebra Comput., June, 2023

On the Descriptive Complexity of Temporal Constraint Satisfaction Problems.

Manuel Bodirsky, Jakub Rydval

J. ACM, February, 2023

Forbidden Tournaments and the Orientation Completion Problem.

Manuel Bodirsky, Santiago Guzmán-Pro

CoRR, 2023

The smallest hard trees.

Manuel Bodirsky, Jakub Bulín, Florian Starke, Michael Wernthaler

Constraints An Int. J., 2023

Network Satisfaction Problems Solved by k-Consistency.

Manuel Bodirsky, Simon Knäuer

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Maximal Digraphs with Respect to Primitive Positive Constructability.

Manuel Bodirsky, Florian Starke

Comb., December, 2022

Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation.

Manuel Bodirsky, Marcello Mamino, Caterina Viola

ACM Trans. Comput. Log., 2022

Tractable Combinations of Temporal CSPs.

Manuel Bodirsky, Johannes Greiner, Jakub Rydval

Log. Methods Comput. Sci., 2022

The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom.

Manuel Bodirsky, Simon Knäuer

J. Artif. Intell. Res., 2022

2021

A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP.

Manuel Bodirsky, Florent R. Madelaine, Antoine Mottet

SIAM J. Comput., 2021

Projective clone Homomorphisms.

Manuel Bodirsky, Michael Pinsker, András Pongrácz

J. Symb. Log., 2021

Solving equation systems in ω-categorical algebras.

Manuel Bodirsky, Thomas Quinn-Gregson

J. Math. Log., 2021

Smooth digraphs modulo primitive positive constructability and cyclic loop conditions.

Manuel Bodirsky, Florian Starke, Albert Vucaj

Int. J. Algebra Comput., 2021

Universal Horn Sentences and the Joint Embedding Property.

Manuel Bodirsky, Jakub Rydval, André Schrottenloher

Discret. Math. Theor. Comput. Sci., 2021

Amalgamation is Undecidable.

Manuel Bodirsky, Simon Knäuer, Jakub Rydval

CoRR, 2021

Canonical functions: a proof via topological dynamics.

Michael Pinsker, Manuel Bodirsky

Contributions Discret. Math., 2021

On Logics and Homomorphism Closure.

Manuel Bodirsky, Thomas Feller, Simon Knäuer, Sebastian Rudolph

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

Canonical Polymorphisms of Ramsey Structures and the Unique Interpolation Property.

Manuel Bodirsky, Bertalan Bodor

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

Tractable Combinations of Theories via Sampling.

Manuel Bodirsky, Johannes Greiner

Proceedings of the Logics in Artificial Intelligence - 17th European Conference, 2021

Datalog-Expressibility for Monadic and Guarded Second-Order Logic.

Manuel Bodirsky, Simon Knäuer, Sebastian Rudolph

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom.

Manuel Bodirsky, Simon Knäuer

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020

The Complexity of Combinations of Qualitative Constraint Satisfaction Problems.

Manuel Bodirsky, Johannes Greiner

Log. Methods Comput. Sci., 2020

ω-categorical structures avoiding height 1 identities.

Manuel Bodirsky, Antoine Mottet, Miroslav Olsák, Jakub Oprsal, Michael Pinsker, Ross Willard

CoRR, 2020

Piecewise Linear Valued Constraint Satisfaction Problems with Fixed Number of Variables.

Manuel Bodirsky, Marcello Mamino, Caterina Viola

CoRR, 2020

Temporal Constraint Satisfaction Problems in Fixed-Point Logic.

Manuel Bodirsky, Wied Pakusa, Jakub Rydval

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

ASNP: A Tame Fragment of Existential Second-Order Logic.

Manuel Bodirsky, Simon Knäuer, Florian Starke

Proceedings of the Beyond the Horizon of Computability, 2020

Hardness of Network Satisfaction for Relation Algebras with Normal Representations.

Manuel Bodirsky, Simon Knäuer

Proceedings of the Relational and Algebraic Methods in Computer Science, 2020

2019

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs.

Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz

SIAM J. Comput., 2019

Topology is relevant (in the infinite-domain dichotomy conjecture for constraint satisfaction problems).

Manuel Bodirsky, Antoine Mottet, Miroslav Olsák, Jakub Oprsal, Michael Pinsker, Ross Willard

CoRR, 2019

Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems).

Manuel Bodirsky, Antoine Mottet, Miroslav Olsák, Jakub Oprsal, Michael Pinsker, Ross Willard

Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, 2019

2018

Tropically Convex Constraint Satisfaction.

Manuel Bodirsky, Marcello Mamino

Theory Comput. Syst., 2018

The universal homogeneous binary tree.

Manuel Bodirsky, David Bradley-Williams, Michael Pinsker, András Pongrácz

J. Log. Comput., 2018

A Dichotomy for First-Order Reducts of Unary Structures.

Manuel Bodirsky, Antoine Mottet

Log. Methods Comput. Sci., 2018

Discrete Temporal Constraint Satisfaction Problems.

Manuel Bodirsky, Barnaby Martin, Antoine Mottet

J. ACM, 2018

A polynomial-time algorithm for median-closed semilinear constraints.

Manuel Bodirsky, Marcello Mamino

CoRR, 2018

The Complexity of Disjunctive Linear Diophantine Constraints.

Manuel Bodirsky, Barnaby Martin, Marcello Mamino, Antoine Mottet

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP.

Manuel Bodirsky, Florent R. Madelaine, Antoine Mottet

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

Classification Transfer for Qualitative Reasoning Problems.

Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains.

Manuel Bodirsky, Marcello Mamino, Caterina Viola

Proceedings of the 27th EACSL Annual Conference on Computer Science Logic, 2018

Finite Relation Algebras with Normal Representations.

Manuel Bodirsky

Proceedings of the Relational and Algebraic Methods in Computer Science, 2018

2017

The Complexity of Phylogeny Constraint Satisfaction Problems.

Manuel Bodirsky, Peter Jonsson, Van Trung Pham

ACM Trans. Comput. Log., 2017

A Model-Theoretic View on Qualitative Constraint Reasoning.

Manuel Bodirsky, Peter Jonsson

J. Artif. Intell. Res., 2017

Constraint Satisfaction Problems over Numeric Domains.

Manuel Bodirsky, Marcello Mamino

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016

Reducts of Structures and Maximal-Closed Permutation Groups.

Manuel Bodirsky, Dugald Macpherson

J. Symb. Log., 2016

The Reducts of the homogeneous Binary Branching C-Relation.

Manuel Bodirsky, Peter Jonsson, Van Trung Pham

J. Symb. Log., 2016

Distance constraint satisfaction problems.

Manuel Bodirsky, Víctor Dalmau, Barnaby Martin, Antoine Mottet, Michael Pinsker

Inf. Comput., 2016

The Complexity of Phylogeny Constraint Satisfaction.

Manuel Bodirsky, Peter Jonsson, Van Trung Pham

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction.

Manuel Bodirsky, Antoine Mottet

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

Max-Closed Semilinear Constraint Satisfaction.

Manuel Bodirsky, Marcello Mamino

Proceedings of the Computer Science - Theory and Applications, 2016

2015

Schaefer's Theorem for Graphs.

Manuel Bodirsky, Michael Pinsker

J. ACM, 2015

The Complexity of Constraint Satisfaction Problems (Invited Talk).

Manuel Bodirsky

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Constraint Satisfaction Problems over the Integers with Successor.

Manuel Bodirsky, Barnaby Martin, Antoine Mottet

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Ramsey classes: examples and constructions.

Manuel Bodirsky

Proceedings of the Surveys in Combinatorics 2015, 2015

2014

Tractability of quantified temporal constraints to the max.

Manuel Bodirsky, Hubie Chen, Michal Wrona

Int. J. Algebra Comput., 2014

New Ramsey Classes from Old.

Manuel Bodirsky

Electron. J. Comb., 2014

2013

Constraint satisfaction tractability from semi-lattice operations on infinite sets.

Manuel Bodirsky, H. Dugald Macpherson, Johan Thapper

ACM Trans. Comput. Log., 2013

Complexity of existential positive first-order logic.

Manuel Bodirsky, Miki Hermann, Florian Richoux

J. Log. Comput., 2013

Decidability of definability.

Manuel Bodirsky, Michael Pinsker, Todor Tsankov

J. Symb. Log., 2013

Datalog and constraint satisfaction with infinite templates.

Manuel Bodirsky, Víctor Dalmau

J. Comput. Syst. Sci., 2013

Reconstructing the topology of clones.

Manuel Bodirsky, Michael Pinsker, András Pongrácz

CoRR, 2013

2012

On the Complexity of MMSNP.

Manuel Bodirsky, Hubie Chen, Tomás Feder

SIAM J. Discret. Math., 2012

Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction.

Manuel Bodirsky, Peter Jonsson, Timo von Oertzen

J. Log. Comput., 2012

Tractable Set Constraints.

Manuel Bodirsky, Martin Hils

J. Artif. Intell. Res., 2012

The complexity of surjective homomorphism problems - a survey.

Manuel Bodirsky, Jan Kára, Barnaby Martin

Discret. Appl. Math., 2012

Essential Convexity and Complexity of Semi-Algebraic Constraints

Manuel Bodirsky, Peter Jonsson, Timo von Oertzen

Log. Methods Comput. Sci., 2012

Topological Birkhoff

Manuel Bodirsky, Michael Pinsker

CoRR, 2012

Complexity Classification in Infinite-Domain Constraint Satisfaction

Manuel Bodirsky

CoRR, 2012

Equivalence Constraint Satisfaction Problems.

Manuel Bodirsky, Michal Wrona

Proceedings of the Computer Science Logic (CSL'12), 2012

2011

Limit Behavior of Locally Consistent Constraint Satisfaction Problems.

Manuel Bodirsky, Daniel Král'

SIAM J. Discret. Math., 2011

Boltzmann Samplers, Pólya Theory, and Cycle Pointing.

Manuel Bodirsky, Éric Fusy, Mihyun Kang, Stefan Vigerske

SIAM J. Comput., 2011

The Complexity of Rooted Phylogeny Problems

Manuel Bodirsky, Jens K. Müller

Log. Methods Comput. Sci., 2011

RCC8 Is Polynomial on Networks of Bounded Treewidth.

Manuel Bodirsky, Stefan Wölfl

Proceedings of the IJCAI 2011, 2011

Tractable Set Constraints.

Manuel Bodirsky, Martin Hils, Alex Krimkevitch

Proceedings of the IJCAI 2011, 2011

2010

A fast algorithm and datalog inexpressibility for temporal reasoning.

Manuel Bodirsky, Jan Kára

ACM Trans. Comput. Log., 2010

Peek arc consistency.

Manuel Bodirsky, Hubie Chen

Theor. Comput. Sci., 2010

Quantified Equality Constraints.

Manuel Bodirsky, Hubie Chen

SIAM J. Comput., 2010

The reducts of equality up to primitive positive interdefinability.

Manuel Bodirsky, Hubie Chen, Michael Pinsker

J. Symb. Log., 2010

The complexity of temporal constraint satisfaction problems.

Manuel Bodirsky, Jan Kára

J. ACM, 2010

Distance Constraint Satisfaction Problems.

Manuel Bodirsky, Víctor Dalmau, Barnaby Martin, Michael Pinsker

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009

Maximal infinite-valued constraint languages.

Manuel Bodirsky, Hubie Chen, Jan Kára, Timo von Oertzen

Theor. Comput. Sci., 2009

Qualitative Temporal and Spatial Reasoning Revisited.

Manuel Bodirsky, Hubie Chen

J. Log. Comput., 2009

Integer programming with 2-variable equations and 1-variable inequalities.

Manuel Bodirsky, Gustav Nordh, Timo von Oertzen

Inf. Process. Lett., 2009

On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction

Manuel Bodirsky, Martin Hils, Barnaby Martin

Log. Methods Comput. Sci., 2009

Relatively quantified constraint satisfaction.

Manuel Bodirsky, Hubie Chen

Constraints An Int. J., 2009

Semilinear Program Feasibility.

Manuel Bodirsky, Peter Jonsson, Timo von Oertzen

Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

Reducts of Ramsey Structures.

Manuel Bodirsky, Michael Pinsker

Proceedings of the Model Theoretic Methods in Finite Combinatorics, 2009

2008

Generating unlabeled connected cubic planar graphs uniformly at random.

Manuel Bodirsky, Clemens Gröpl, Mihyun Kang

Random Struct. Algorithms, 2008

The Complexity of Equality Constraint Languages.

Manuel Bodirsky, Jan Kára

Theory Comput. Syst., 2008

A Fast Algorithm and Lower Bound for Temporal Reasoning

Manuel Bodirsky, Jan Kára

CoRR, 2008

Non-dichotomies in Constraint Satisfaction Complexity.

Manuel Bodirsky, Martin Grohe

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Constraint Satisfaction Problems with Infinite Templates.

Manuel Bodirsky

Proceedings of the Complexity of Constraints, 2008

2007

Generating labeled planar graphs uniformly at random.

Manuel Bodirsky, Clemens Gröpl, Mihyun Kang

Theor. Comput. Sci., 2007

Random cubic planar graphs.

Manuel Bodirsky, Mihyun Kang, Mike Löffler, Colin McDiarmid

Random Struct. Algorithms, 2007

Cores of Countably Categorical Structures.

Manuel Bodirsky

Log. Methods Comput. Sci., 2007

Enumeration and limit laws for series-parallel graphs.

Manuel Bodirsky, Omer Giménez, Mihyun Kang, Marc Noy

Eur. J. Comb., 2007

Enumeration and Asymptotic Properties of Unlabeled Outerplanar Graphs.

Manuel Bodirsky, Éric Fusy, Mihyun Kang, Stefan Vigerske

Electron. J. Comb., 2007

Determining the consistency of partial tree descriptions.

Manuel Bodirsky, Martin Kutz

Artif. Intell., 2007

An unbiased pointing operator for unlabeled structures, with applications to counting and sampling.

Manuel Bodirsky, Éric Fusy, Mihyun Kang, Stefan Vigerske

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Constraint Satisfaction with Countable Homogeneous Templates.

Manuel Bodirsky, Jaroslav Nesetril

J. Log. Comput., 2006

Generating Outerplanar Graphs Uniformly at Random.

Manuel Bodirsky, Mihyun Kang

Comb. Probab. Comput., 2006

Collapsibility in Infinite-Domain Quantified Constraint Satisfaction.

Manuel Bodirsky, Hubie Chen

Proceedings of the Computer Science Logic, 20th International Workshop, 2006

2005

Locally Consistent Constraint Satisfaction Problems with Binary Constraints.

Manuel Bodirsky, Daniel Král

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2005

The Core of a Countably Categorical Structure.

Manuel Bodirsky

Proceedings of the STACS 2005, 2005

Sampling Unlabeled Biconnected Planar Graphs.

Manuel Bodirsky, Clemens Gröpl, Mihyun Kang

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

2004

Constraint satisfaction with infinite domains.

Manuel Bodirsky

PhD thesis, 2004

A new algorithm for normal dominance constraints.

Manuel Bodirsky, Denys Duchier, Joachim Niehren, Sebastian Miele

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Effciently Computing the Density of Regular Languages.

Manuel Bodirsky, Tobias Gärtner, Timo von Oertzen, Jan Schwinghammer

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

2002

Pure Dominance Constraints.

Manuel Bodirsky, Martin Kutz

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

2001

Beta Reduction Constraints.

Manuel Bodirsky, Katrin Erk, Alexander Koller, Joachim Niehren

Proceedings of the Rewriting Techniques and Applications, 12th International Conference, 2001

Underspecified Beta Reduction.

Manuel Bodirsky, Katrin Erk, Alexander Koller, Joachim Niehren

Proceedings of the Association for Computational Linguistic, 2001