NOTE:  All workshop lectures will be held in Room 1308 of the Stevenson Center on the Vanderbilt campus.  Click here for a campus map.

AIM & SCOPE

The Constraint Satisfaction Problem (CSP) provides a framework for expressing a large number of combinatorial search problems that arise in wide areas of computer science and discrete mathematics, including artificial intelligence, database theory, scheduling and
networking. Graph colorability and Boolean satisfiability are two examples of the many problems that have a natural expression as instances of the CSP.

While the general class of CSPs is known to be NP-complete, certain natural subclasses of this collection of problems have been identified as being tractable and it is a central problem in the study of CSPs  to identify these ``islands of tractability''.  The work of Jeavons and his co-authors has brought to light a very deep connection between universal algebra and the CSP that has the potential to resolve this and other open problems in the area. At the heart of this approach is a method to associate to each natural subclass of the CSP a finite algebraic structure in a way that effectively translates questions of computational complexity into the realm of universal algebra.

The primary goal of this workshop is to bring together researchers from the universal algebra/lattice theory and CSP communities to further the algebraic approach to the CSP.  Secondary goals are to foster and strengthen links between computer science and mathematics and to provide graduate students and junior researchers with a rich and interesting set of new problems to work on.

This workshop follows immediately after the International Conference on Order, Algebra, and Logics and the 22nd Shanks Lecture.  The OAL conference will run from June 12-16, 2007 and participants of the workshop are encouraged to attend the OAL conference.

STRUCTURE OF THE WORKSHOP

The workshop will run from Sunday, June 17 to Wednesday, June 20. Sessions will generally start at 9:00am and end by 5:30pm. Tutorials will be offered to provide participants with the requisite background material and then a series of invited lectures on recent work on the CSP and algebra will be given.  A limited number of contributed talks will be presented during the workshop.

Background Material

Those participants who wish to obtain some background information on the Constraint Satisfaction Problem prior to the start of the workshop could consider reading over the slides of the following recent presentations on the CSP:

Peter Jeavons (Tutorial on the CSP and algebra, Oxford 2006),  Andrei Bulatov (CSP, algebras, varieties, Oxford, 2006), Phokion Kolaitis (Tutorial on Constraint Satisfaction, Complexity, and Logic,   Logic Colloquium 2005).

This paper by Bulatov, Jeavons, and Krokhin also provides a good introduction to the subject, from an algebraic point of view.


CONTACT

Please visit this site for additional information and regular updates, and use the conference e-mail address uacsp2007@vanderbilt.edu to reach the organizers.