An Isaac Newton Institute Satellite Workshop - University of Oxford

Mathematics of Constraint Satisfaction:

Algebra, Logic and Graph Theory

20 - 24 March 2006

Organisers: Peter Jeavons (Oxford) and Andrei Krokhin (Durham)

Scientific Enquiries: Andrei Krokhin

in association with the Newton Institute programme entitled Logic and Algorithms

Programme | Participants

Theme of Conference:

The study of constraint satisfaction problems (CSPs) began in the 1970's in artificial intelligence, where this paradigm is now as popular as ever, with hundreds of researchers using this framework to model and solve a wide variety of problems. In 1978, Thomas Schaefer published a seminal paper on the complexity classification of Boolean CSPs, and since then the importance of the CSP in theoretical computer science has continued to grow. For example, many standard complete problems for standard complexity classes are variants of CSPs, and some of the first optimal inapproximability results in combinatorial optimization were proved for certain CSPs.

During the last 10 years, researchers studying the complexity of CSPs have discovered deep connections between this framework and many areas of mathematics, the strongest links currently being with universal algebra and lattice theory, logic and finite model theory, and graph theory and combinatorics. The corner-stone of logical and combinatorial approaches to CSP is the fact that many questions about constraint satisfaction can be stated as questions about homomorphisms between relational structures (e.g., graphs). The universal-algebraic approach assigns a finite algebra to every CSP and employs the properties of the algebra to study the properties of the CSP.

The workshop will consist of three 1.5-hour tutorials (one on each topic of the workshop) outlining the basics of the three mathematical approaches to CSP, 11 1-hour research expositions providing state-of-the-art information on mathematical developments related to constraint satisfaction, and a number of 30-minute talks on current research.

The purpose of the workshop is to:

  • enhance the synergy between different mathematical aspects of CSP research
  • form new connections between theoretical researchers and more applied researchers working on constraint satisfaction
  • provide the participants with the state-of-the-art information on the subject of the workshop
  • provide a forum for a comprehensive discussion of mathematical techniques which can be used to analyze the structure of a wide variety of computational problems
  • explore and disseminate new links between Computer Science and Mathematics

Invited Speakers:

Tutorials: Pavol Hell, Peter Jeavons, Phokion Kolaitis.

1-hour lectures: Albert Atserias, Andrei Bulatov, Hubie Chen, Nadia Creignou, Victor Dalmau, Georg Gottlob, Johan Hastad, Peter Jonsson, Benoit Larose, Jaroslav Nesetril, Iain Stewart.

Short talks: Manuel Bodirsky, David Cohen, Steve Linton, Daniel Marx, Francesca Rossi, Barbara Smith, Thomas Schiex, Pascal Tesson, Dimitrios Thilikos, Heribert Vollmer.

Location and Cost:

The workshop will take place in St. Anne's College, University of Oxford. The conference package, costing £410, includes en-suite rooms, coffee breaks, breakfast, lunch, dinner, from lunch on Monday 20 March to breakfast on Friday 24 March 2006. A non-residential package, costing £60 and including only coffee breaks and lunches 20-23 March, is also available.

Applications Forms and Further Information:

Are available here. Invited participants to the semester long programme are asked to also apply.

Closing Date:

The closing date for the receipt of applications is 31 October 2005

Logic and Algorithms | Workshops | Newton Institute Home Page