The Classification Program for Counting Problems

   Lecture 1: The Classification Program for Counting Problems I
   Lecture 2: The Classification Program for Counting Problems II
   Lecture 3: The Classification Program for Counting Problems III
 

 

This series of talks is part of the Counting Complexity and Phase Transitions Boot Camp


Speaker: Jin-Yi Cai (University of Wisconsin) and Heng Guo (Queen Mary, University of London) 

This mini-course will begin with an introduction to the Fisher-Kasteleyn-Temperley algorithm, matchgates, and Valiant's holographic algorithms.  It will then discuss dichotomy theorems for #CSP and Holant problems on the boolean domain.  The final session will discuss the question of whether FKT and holographic algorithms are universal for planar counting problems.