Since September 2015, I am a doctoral student enrolled in the QuantLA doctoral program and
working at the institute of algebra at the Technische Universität Dresden under the supervision of
I am currently working on decision problems that can be formulated as constraint satisfaction problems over an infinite domain. More specifically, I am focussing on constraint satisfaction problems over the integers and whose constraint languages can be formulated in first-order arithmetic. These problems come from various areas of computer science, such as artificial intelligence or verification. The methods involved in the study of these problems come from several areas of mathematics such as universal algebra, topology, model theory, and Ramsey theory.
A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP.Manuel Bodirsky, Florent Madelaine, Antoine Mottet.
Proceedings of LICS 2018. Abstract
The logic MMSNP is a restricted fragment of existential second-order logic which allows to express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi who showed that every MMSNP sentence is computationally equivalent to a finite-domain constraint satisfaction problem (CSP); the involved probabilistic reductions were derandomized by Kun using explicit constructions of expander structures. We present a new proof of the reduction to finite-domain CSPs that does not rely on the results of Kun. This new proof allows us to obtain a stronger statement and to verify the more general Bodirsky-Pinsker dichotomy conjecture for CSPs in MMSNP. Our approach uses the fact that every MMSNP sentencedescribes a finite union of CSPs for countable categorical structures; moreover, by a recent result of Hubička and Nešetřil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property. This allows us to use the universal-algebraic approach to study the computational complexity of MMSNP.
A Dichotomy for First-Order Reducts of Unary Structures.Manuel Bodirsky, Antoine Mottet.
In Logical Methods in Computer Science 14(2). Abstract
Many natural decision problems can be formulated as constraint satisfaction problems for reducts A of finitely bounded homogeneous structures. This class of problems is a large generalisation of the class of CSPs over finite domains. Our first result is a general polynomial-time reduction from such infinite-domain CSPs to finite-domain CSPs. We use this reduction to obtain new powerful polynomial-time tractability conditions that can be expressed in terms of the topological polymorphism clone of A. Moreover, we study the subclass C of CSPs for structures A that are reducts of a structure with a unary language. Also this class C properly extends the class of all finite-domain CSPs. We apply our new tractability conditions to prove the general tractability conjecture of Bodirsky and Pinsker for reducts of finitely bounded homogeneous structures for the class C.
Discrete Temporal Constraint Satisfaction Problems.Manuel Bodirsky, Barnaby Martin, Antoine Mottet.
In Journal of the ACM 65(2). Abstract
A discrete temporal constraint satisfaction problem is a constraint satisfaction problem (CSP) over the set of integers whose constraint language consists of relations that are first-order definable over the order of the integers. We prove that every discrete temporal CSP is in P or NP-complete, unless it can be formulated as a finite domain CSP, in which case the computational complexity is not known in general.
Seminars, conferences, workshopsFuture events:
- 27-31/08/18: QuantLA Workshop, Meissen.
- 14-16/09/18: Colloquium Logicum, Bayreuth.
- 18-23/11/18: Unifying Themes in Ramsey Theory, Banff.