Manuel Bodirsky

Affiliations:
  • TU Dresden, Institut für Algebra, Germany
  • École Polytechnique, Paris, France (former)


According to our database1, Manuel Bodirsky authored at least 112 papers between 2001 and 2023.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
The lattice of clones of self-dual operations collapsed.
Int. J. Algebra Comput., June, 2023

On the Descriptive Complexity of Temporal Constraint Satisfaction Problems.
J. ACM, February, 2023

The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems.
CoRR, 2023

Forbidden Tournaments and the Orientation Completion Problem.
CoRR, 2023

The smallest hard trees.
Constraints An Int. J., 2023

Network Satisfaction Problems Solved by k-Consistency.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022
Maximal Digraphs with Respect to Primitive Positive Constructability.
Comb., December, 2022

Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation.
ACM Trans. Comput. Log., 2022

Tractable Combinations of Temporal CSPs.
Log. Methods Comput. Sci., 2022

The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom.
J. Artif. Intell. Res., 2022

Complexity Classification Transfer for CSPs via Algebraic Products.
CoRR, 2022

2021
A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP.
SIAM J. Comput., 2021

Projective clone Homomorphisms.
J. Symb. Log., 2021

Solving equation systems in ω-categorical algebras.
J. Math. Log., 2021

Smooth digraphs modulo primitive positive constructability and cyclic loop conditions.
Int. J. Algebra Comput., 2021

Universal Horn Sentences and the Joint Embedding Property.
Discret. Math. Theor. Comput. Sci., 2021

Amalgamation is Undecidable.
CoRR, 2021

Canonical functions: a proof via topological dynamics.
Contributions Discret. Math., 2021

On Logics and Homomorphism Closure.
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

Canonical Polymorphisms of Ramsey Structures and the Unique Interpolation Property.
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

Tractable Combinations of Theories via Sampling.
Proceedings of the Logics in Artificial Intelligence - 17th European Conference, 2021

Datalog-Expressibility for Monadic and Guarded Second-Order Logic.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom.
Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020
The Complexity of Combinations of Qualitative Constraint Satisfaction Problems.
Log. Methods Comput. Sci., 2020

ω-categorical structures avoiding height 1 identities.
CoRR, 2020

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

Temporal Constraint Satisfaction Problems in Fixed-Point Logic.
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.
Proceedings of the Beyond the Horizon of Computability, 2020

Hardness of Network Satisfaction for Relation Algebras with Normal Representations.
Proceedings of the Relational and Algebraic Methods in Computer Science, 2020

2019
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs.
SIAM J. Comput., 2019

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

Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems).
Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, 2019

2018
Tropically Convex Constraint Satisfaction.
Theory Comput. Syst., 2018

The universal homogeneous binary tree.
J. Log. Comput., 2018

A Dichotomy for First-Order Reducts of Unary Structures.
Log. Methods Comput. Sci., 2018

Discrete Temporal Constraint Satisfaction Problems.
J. ACM, 2018

A polynomial-time algorithm for median-closed semilinear constraints.
CoRR, 2018

The Complexity of Disjunctive Linear Diophantine Constraints.
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.
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

Classification Transfer for Qualitative Reasoning Problems.
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains.
Proceedings of the 27th EACSL Annual Conference on Computer Science Logic, 2018

Finite Relation Algebras with Normal Representations.
Proceedings of the Relational and Algebraic Methods in Computer Science, 2018

2017
The Complexity of Phylogeny Constraint Satisfaction Problems.
ACM Trans. Comput. Log., 2017

A Model-Theoretic View on Qualitative Constraint Reasoning.
J. Artif. Intell. Res., 2017

Constraint Satisfaction Problems over Numeric Domains.
Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016
Reducts of Structures and Maximal-Closed Permutation Groups.
J. Symb. Log., 2016

The Reducts of the homogeneous Binary Branching C-Relation.
J. Symb. Log., 2016

Distance constraint satisfaction problems.
Inf. Comput., 2016

The Complexity of Phylogeny Constraint Satisfaction.
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.
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

Max-Closed Semilinear Constraint Satisfaction.
Proceedings of the Computer Science - Theory and Applications, 2016

2015
Schaefer's Theorem for Graphs.
J. ACM, 2015

The Complexity of Constraint Satisfaction Problems (Invited Talk).
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Constraint Satisfaction Problems over the Integers with Successor.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Ramsey classes: examples and constructions.
Proceedings of the Surveys in Combinatorics 2015, 2015

2014
Tractability of quantified temporal constraints to the max.
Int. J. Algebra Comput., 2014

New Ramsey Classes from Old.
Electron. J. Comb., 2014

2013
Constraint satisfaction tractability from semi-lattice operations on infinite sets.
ACM Trans. Comput. Log., 2013

Complexity of existential positive first-order logic.
J. Log. Comput., 2013

Decidability of definability.
J. Symb. Log., 2013

Datalog and constraint satisfaction with infinite templates.
J. Comput. Syst. Sci., 2013

Reconstructing the topology of clones.
CoRR, 2013

2012
On the Complexity of MMSNP.
SIAM J. Discret. Math., 2012

Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction.
J. Log. Comput., 2012

Tractable Set Constraints.
J. Artif. Intell. Res., 2012

The complexity of surjective homomorphism problems - a survey.
Discret. Appl. Math., 2012

Essential Convexity and Complexity of Semi-Algebraic Constraints
Log. Methods Comput. Sci., 2012

Topological Birkhoff
CoRR, 2012

Complexity Classification in Infinite-Domain Constraint Satisfaction
CoRR, 2012

Equivalence Constraint Satisfaction Problems.
Proceedings of the Computer Science Logic (CSL'12), 2012

2011
Limit Behavior of Locally Consistent Constraint Satisfaction Problems.
SIAM J. Discret. Math., 2011

Boltzmann Samplers, Pólya Theory, and Cycle Pointing.
SIAM J. Comput., 2011

The Complexity of Rooted Phylogeny Problems
Log. Methods Comput. Sci., 2011

RCC8 Is Polynomial on Networks of Bounded Treewidth.
Proceedings of the IJCAI 2011, 2011

Tractable Set Constraints.
Proceedings of the IJCAI 2011, 2011

2010
A fast algorithm and datalog inexpressibility for temporal reasoning.
ACM Trans. Comput. Log., 2010

Peek arc consistency.
Theor. Comput. Sci., 2010

Quantified Equality Constraints.
SIAM J. Comput., 2010

The reducts of equality up to primitive positive interdefinability.
J. Symb. Log., 2010

The complexity of temporal constraint satisfaction problems.
J. ACM, 2010

Distance Constraint Satisfaction Problems.
Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009
Maximal infinite-valued constraint languages.
Theor. Comput. Sci., 2009

Qualitative Temporal and Spatial Reasoning Revisited.
J. Log. Comput., 2009

Integer programming with 2-variable equations and 1-variable inequalities.
Inf. Process. Lett., 2009

On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
Log. Methods Comput. Sci., 2009

Relatively quantified constraint satisfaction.
Constraints An Int. J., 2009

Semilinear Program Feasibility.
Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

Reducts of Ramsey Structures.
Proceedings of the Model Theoretic Methods in Finite Combinatorics, 2009

2008
Generating unlabeled connected cubic planar graphs uniformly at random.
Random Struct. Algorithms, 2008

The Complexity of Equality Constraint Languages.
Theory Comput. Syst., 2008

A Fast Algorithm and Lower Bound for Temporal Reasoning
CoRR, 2008

Non-dichotomies in Constraint Satisfaction Complexity.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Constraint Satisfaction Problems with Infinite Templates.
Proceedings of the Complexity of Constraints, 2008

2007
Generating labeled planar graphs uniformly at random.
Theor. Comput. Sci., 2007

Random cubic planar graphs.
Random Struct. Algorithms, 2007

Cores of Countably Categorical Structures.
Log. Methods Comput. Sci., 2007

Enumeration and limit laws for series-parallel graphs.
Eur. J. Comb., 2007

Enumeration and Asymptotic Properties of Unlabeled Outerplanar Graphs.
Electron. J. Comb., 2007

Determining the consistency of partial tree descriptions.
Artif. Intell., 2007

An unbiased pointing operator for unlabeled structures, with applications to counting and sampling.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
Constraint Satisfaction with Countable Homogeneous Templates.
J. Log. Comput., 2006

Generating Outerplanar Graphs Uniformly at Random.
Comb. Probab. Comput., 2006

Collapsibility in Infinite-Domain Quantified Constraint Satisfaction.
Proceedings of the Computer Science Logic, 20th International Workshop, 2006

2005
Locally Consistent Constraint Satisfaction Problems with Binary Constraints.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2005

The Core of a Countably Categorical Structure.
Proceedings of the STACS 2005, 2005

Sampling Unlabeled Biconnected Planar Graphs.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

2004
Constraint satisfaction with infinite domains.
PhD thesis, 2004

A new algorithm for normal dominance constraints.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Effciently Computing the Density of Regular Languages.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

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

2001
Beta Reduction Constraints.
Proceedings of the Rewriting Techniques and Applications, 12th International Conference, 2001

Underspecified Beta Reduction.
Proceedings of the Association for Computational Linguistic, 2001


  Loading...