# Antoine Mottet

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
Manuel Bodirsky.

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.

# Selected Papers

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

Manuel Bodirsky, Florent Madelaine, Antoine Mottet.

Accepted for publication at 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, workshops

Future events:- 09-12/07/18: LICS 2018, Oxford.
- 15-20/07/18: Ramsey Theory in Logic, Combinatorics and Complexity, Bertinoro.
- 27-31/08/18: QuantLA Workshop.

- 07/06/18: A universal-algebraic proof of the dichotomy for MMSNP.
Slides

The constraint satisfaction problem: complexity and approximability, Dagstuhl seminar. - 02/06/18: Cyclic terms, CSP, MMSNP. Slides

Arbeitstagung Allgemeine Algebra, Darmstadt. - 07/02/18: Proof of the universal-algebraic conjecture for MMSNP. Slides

Joint Dresden-Prague algebra seminar, Prague. - 07/11/17: Introduction to Constraint Satisfaction Problems.

QuantLA seminar, Leipzig. - 22/09/17: Towards a proof of the universal-algebraic conjecture for MMSNP.

QuantLA Workshop, Altenberg. - 01/09/17: Towards a proof of the universal-algebraic conjecture for MMSNP.

International Seminar of the Institute of Algebra, TU Dresden. - 19/06/17: Discrete Temporal Constraint Satisfaction Problems. Slides

Workshop on Logic and Computational Complexity, Reykjavik. - 12-14/06/17: 11th Joint Workshop of the German Research Training in Computer Science.
- 22/03/17: The universal-algebraic approach to constraint satisfaction for countable saturated structures.

KAFKA seminar, Charles University, Prague. - 09/11/16: Canonical functions and constraint satisfaction. Slides Video

Workshop {Symmetry, Logic, Computation}, Simons Institute, Berkeley. - 19/09/16: Reasoning with discrete time. Slides

QuantLA Workshop, Krippen. - 07/07/16: Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction.

31st Annual Symposium of Logic in Computer Science (LICS16), New-York. - 11/05/16: Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction.
Slides

PhDs in Logic VIII, Darmstadt. - 26/04/16: Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction. Slides

QuantLA seminar, Dresden. - 04/12/15: Mashup algebras and constraint satisfaction problems.

Seminar of the institute of algebra, Dresden. - 06/07/15: Constraint Satisfaction Problems over the Integers with Successor. Slides

42nd International Colloquium on Automata, Languages and Programming (ICALP15), Kyoto.

# Other things

- Has P vs. NP been solved? (by Scott Aaronson)
- Tractability of Constraint Satisfaction Problems and Projective Clone Homomorphisms. Link
- Dichotomies in Constraint Satisfaction: Canonical Functions and Numeric CSPs. PhD dissertation
- An interactive illustration of mean-payoff games.