Technion
 
         Computer Science Colloquium
 
Time+Place : Tuesday 03/01/2012 14:30 room 337-8 Taub  Bld.
Speaker    : Andrei Bulatov
Affiliation: School of Computing Science, Simon Fraser University,
             Vancouver, Canada
Host       : Johann Makowsky
Title      : The complexity of counting constraint satisfaction problem
 
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
 
----------------------------------------------------------
Visit our home page-   <http://www.cs.technion.ac.il/~colloq>
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Hadas Heier   <heier@cs.technion.ac.il>