Outline
The symposium we propose will explore mathematical, algorithmic, and complexity-theoretic aspects of CSPs. Even in the past decade, deep mathematical theories have been developed with the aim to explain the mathematical structure that makes CSPs hard or easy to solve, either exactly or approximately. Some spectacular progress has been made, but many central problems are still open.
The symposium will bring together specialists using algebraic, logical, combinatorial, analytical, categorical, and topological approaches to the CSP. One particular topic of the symposium will be the emerging area of the promise CSPs, which was previously studied mostly in the special case of approximate graph and hypergraph colouring. This new direction links together all the existing approaches, from universal algebra to probabilistically checkable proofs, and it already uncovered new connections, e.g., to topological combinatorics. The main aim of the workshop is to foster further synergy between different approaches in the rich area of mathematics of constraint satisfaction.
About Durham Symposia
The Durham Symposia began in 1974 (as the LMS Durham Symposia) and have now become an established and recognised series of international research meetings, having celebrated its 111th symposium. They provide an excellent opportunity to explore an area of research in depth, to learn of new developments, and to instigate links between different branches.