Smooth Approximations in Constraint Satisfaction

• Applicant: Dr. Antoine Mottet
• Subject Area: Theoretical Computer Science
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 534904934

A constraint satisfaction problem is a computational problem where, given a set of constraints and variables ranging over a domain, the task is to decide whether there exist values for the variables that satisfy all the constraints. Such problems are central in theoretical and applied computer science and the systematic study of their complexity by means of algebraic tools has been a very active field of research in the last three decades. The project aims at investigating constraint satisfaction problems in the case where the domain of values for the variables is infinite. A number of algorithmic and algebraic questions exist in this field and recently a new theory, called the theory of smooth approximations, has been put forward as a tool to answer these questions. The objectives of the project are two fold: - use the existing theory to solve the problems that are at the frontier of what is currently known, and which are motivated by applications in artificial intelligence and knowledge reasoning, - develop the theory further to make progress on a proof of the so-called infinite-domain tractability conjecture by Bodirsky and Pinsker.

• DFG Programme: Research Grants