ERC starting grant "CSP-Complexity"

CSP-Complexity was a research project funded by the European Research Council (ERC) as starting grant 257039, ERC-2010-StG_20091028. The project has first been hosted by the CNRS, via the Laboratoire d'Informatique de l'École Polytechnique (LIX) as part of the Algorithms and Complexity Team, and then, since summer 2014, at the institute of algebra of TU Dresden.

• The principal investigator is Manuel Bodirsky.
• The full title of the project is ``Constraint Satisfaction Problems: Algorithms and Complexity''
• The project started 01/01/2011 and lasted until 30/12/2015.

Project Description

Constraint Satisfaction Problems are computational problems that appear in many areas of computer science, for example in optimisation, scheduling, database theory, and knowledge representation. The project CSP-Complexity explored the computational complexity of constraint satisfaction problems: in particular the question which CSPs are polynomial-time tractable. It was already known that classifying the complexity of CSPs is closely related to central questions in universal algebra. One of the outcomes of the project is that universal algebra can also be used when the constraint satisfaction problems are over infinite domains, using concepts and results from model theory and Ramsey theory. This led to several powerful classification results for CSPs over infinite domains, but also to new research directions in the mathematical fields mentioned above.

Team Members

• Manuel Bodirsky, principal investigator.
• Marcello Mamino, postdoc (complexity of algebraic constraint satisfaction problems), since Fall 2013.
• Johannes Greiner, PhD student (polynomial-time decision procedures for CSPs of combinations of theories), since Spring 2015.
• Antoine Mottet, PhD student (The complexity of arithmetic CSPs, QuantLA student), since September 2015.
• Trung Phan Pham, postdoc (reducts of the homogeneous universal C-relation and their polymorphism clones), Fall 2014 -- December 2015.
• Robert Barham, postdoc (reconstruction of countably categorical structures from their endomorphism monoids and polymorphism clones), Fall 2014 -- December 2015.
• François Bossière, PhD student (reducts of the infinite vector space over the two-element field), Fall 2012 -- September 2015.
• Andras Pongracz, postdoc (reducts of homogeneous structures, Ramsey theory), Fall 2012-Fall 2014.
• Nathan Grosshans, research internship, Spring 2013 (convex semi-algebraic constraints).
• Johan Thapper, postdoc from 2010 to 2012 (complexity of algebraic constraint satisfaction problems, valued CSPs).
• Florent Madelaine, MdC en delegation CNRS, 2011-2012 (fragments of existential second-order logic).
• Michal Wrona, visiting postdoc from 01/02/2011 until 30/04/2011 (temporal constraint satisfaction problems, quantified constraint satisfaction).
• Jan Foniok, visiting researcher from February until Summer 2011 (graph homomorphisms and Ramsey theory).