Abstract:

In a constraint satisfaction problem (CSP) we are given a collection of 
variables to be assigned values from a certain set, and a number of 
constraints imposed on allowed combinations of values that the variables 
can be assigned simultaneously. In the counting problem the goal is to 
find the number of assignments satisfying all the constraints.
The counting CSP is an important case of counting problems introduced 
and first studied by Valiant in the late 70s. Various versions of this 
problem have occurred in statistical physics as partition functions, 
combinatorics as the problem of finding the number of certain 
arrangements such as graph homomorphisms, database theory as the number 
of answers to a query, graph theory as the values of various graph 
polynomials, etc. Different aspects of the counting CSP have been 
intensively studied over the last two decades.
In this talk I will survey one line of research on the counting CSP --- 
the complexity of its restricted problems, from small particular cases 
to a complete complexity classification of such problems.

Short Bio:
Andrei Bulatov is an Associate Professor in the School of Computing Science
at Simon Fraser University. He received a PhD in mathematics in 1995 from
the Ural State University in Russia. Prior to coming to Simon Fraser Andrei
Bulatov held appointments at the Ural State university, and the University
of Oxford. His main research area is the constraint satisfaction problem,
where he is mostly known as one of the inventors of the algebraic approach
to constraint problems. This approach has led to a number of results on the
complexity of and algorithms for constraint problems. One of these results
was awarded the best paper award at FOCS. His other research interests
include model theory, counting constraint satisfaction, the complexity of
partition functions.

Refreshments served from 14:15 on,
 	Lecture starts at 14:30