Speaker:

Andrei Bulatov (Simon Fraser University)

Time:

• 16:20-17:20 Beijing Time

• April 25, 2025 (Friday)

Venue:

518, Research Building 4

Abstract:

Counting problems concern computing the number of solutions to combinatorial problems or the total weight of such solutions when weights are involved. Counting problems have a long history starting with partition functions in statistical physics introduced in the beginning of 20th century, to foundational work by Valiant, to a long string of results on approximation of counting problems and partition functions by Jerrum, Sinclair and others, to holographic algorithms by Valiant, to complete complexity classifications by the author, Dyer, Richerby, Cai, and Chen. We review the basics of counting, present the major ideas behind some of the approaches, and mention some notable results.

Speaker Bio:

Dr Bulatov received his PhD in 1995 from the Ural State University in Ekaterinburg, Russia. His early research area was universal algebra and clone theory. When connections between universal algebra and computer science had been discovered, he pioneered the so-called algebraic approach to the Constraint Satisfaction Problem and related fields. In 2000 Dr Bulatov moved, first, to the University of Oxford, and then to Simon Fraser University in Canada, where he works till now. Dr Bulatov is an expert on applications of algebraic methods in computer science. He is a recipient of the 2021 Godel Prize and 2024 Frontiers of Science Award from the International Congress on Basic sciences.