Logic List Mailing Archive

"Algebra, Logic and Graph Theory" (Workshop, Oxford, March 2006)

Isaac Newton Institute for Mathematical Sciences, Cambridge, UK

Satellite Workshop at the University of Oxford

Mathematics of constraint satisfaction:
Algebra, Logic and Graph Theory

(20 - 24 March 2006)

in association with the Newton Institute programme entitled
Logic and Algorithms (16 January to 7 July 2006)

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

Scientific Enquiries: Andrei Krokhin (Durham) - <andrei.krokhin@durham.ac.uk>

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 plenary lectures providing state-of-the-art information on 
mathematical developments related to constraint satisfaction, and a number 
of 30-minute talks on current research.

Invited Speakers:  Tutorials:  P Hell, P Jeavons, Ph Kolaitis.

1-hour lectures: A Atserias, A Bulatov, H Chen, N Creignou, V Dalmau, G
 Gottlob, J Hastad, P Jonsson, B Larose, J Nesetril, I Stewart.

Short talks: M Bodirsky, D Cohen, S Linton, D Marx, F Rossi, B Smith, T
Schiex, P Tesson, D Thilikos, H Vollmer.

Location:  The workshop will take place in St. Anne's College, University
of Oxford.

Application Forms and Further Information:   This can be obtained via the 
following url:
<www.comlab.ox.ac.uk/mathscsp/>

Closing date for applications:   31 October 2005