I am interested in applications of algebraic and model-theoretic methods to the study of problems from theoretical computer science, such as the study of constraint satisfaction problems over infinite domains. I am currently assistant professor in the research group on theoretical computer science at the Hamburg University of Technology.
Selected Papers
Smooth Approximations: an Algebraic Approach to CSPs over finitely bounded homogeneous structures.
Antoine Mottet, Michael Pinsker.
To appear in Journal of the ACM. Preprint Abstract
We develop the novel machinery of smooth approximations and use it to rederive the known P/NP-complete dichotomy results within the scope of the infinite-domain CSP conjecture. Using the same techniques, we also obtain classification results about CSPs solvable by local consistency methods.
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.
Finite Algebras with Hom-Sets of Polynomial Size.
Libor Barto, Antoine Mottet.
To appear in Transactions of the AMS. Abstract
We provide an internal characterization of those finite algebras (i.e., algebraic structures) $\mathbf A$ such that the number of homomorphisms from any finite algebra $\mathbf X$ to $\mathbf A$ is bounded from above by a polynomial in the size of $\mathbf X$. Namely, an algebra $\mathbf A$ has this property if, and only if, no subalgebra of $\mathbf A$ has a nontrivial strongly abelian congruence. We also show that the property can be decided in polynomial time for algebras in finite signatures. Moreover, if $\mathbf A$ is such an algebra, the set of all homomorphisms from $\mathbf X$ to $\mathbf A$ can be computed in polynomial time given $\mathbf X$ as input. As an application of our results to the field of computational complexity, we characterize inherently tractable constraint satisfaction problems over fixed finite structures, i.e., those that are tractable and remain tractable after expanding the fixed structure by arbitrary relations or functions.
Seminars, conferences, workshops
Future events:- 22-28 September: CSP World Congress (organizer), Kolfuschg
- 18-23 May: The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl seminar
