TIME: 11:00-12:00 am,  Friday, October 17, 2008  
 
PLACE: CSE 503  
 
SPEAKER: Michael Molloy
         University of Toronto
 
TITLE: A dichotomy theorem for the resolution complexity of random
       constraint satisfaction problems
 
ABSTRACT: 
Constraint satisfaction problems (CSP's) are generalizations of CNF
boolean formulas.  We are given a set of variables and a domain of
values that the variables can take.  A constraint is a subset of the
variables and a restriction on the values that can be jointly assigned
to those variables.  A CSP is satisfiable if there is an assignment of
values to the variables which does not violate any of the constraints.
Some well-studied special cases are k-SAT, graph colourability and
graph homomorphism. 

Many random models of CSP's appear to be very difficult to solve in
practice.  Chvatal and Szemeredi proved a theorem explaining this for
the case of random 3-SAT: with high probability, the resolution complexity
of a random 3-SAT formula with a linear number of clauses will be
exponentially high.  This implies an exponential lower bound on the
running time of any resolution-based algorithm (such as Davis-Putnam
and its many variants).

In this talk, we discuss a wide family of models of random constraint
satisfaction problems.  The main result is that we determine which models
from this family will, with high probability, have exponentially high
resolution complexity for any linear number of constraints.

Joint work with Siu On Chan, U.C.Berkeley