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>