Abstract
Complexity Theory is the study of intrinsic difficulty of computational problems. One primary goal concerns with the classification of various problems, and P versus NP theory has been the canonical framework. For counting problems the corresponding framework is P versus Valiant’s class #P, which is a quantitative version of NP: Instead of asking whether a problem instance has a solution (the NP type question), it asks how many solutions it has (the #P type question). Many classical problems from statistical physics can also be formulated in this setting, such as the Ising model, Potts model, hardcore gas model, and monomer dimer model. These are sum-of-product computations.
I will give a survey of the classification program for counting problems, of which Prof. Pinyan Lu has been a world leader in this effort. The classification is usually achieved as dichotomy theorems which classify every problem in a broad class into either polynomial time computable (in P), or #P-hard. The classes of problems include counting graph homomorphisms, constraint satisfaction problems, and Holant problems. I will report some new progress (unpublished) on the bounded degree case.
Time
2019-06-18 10:45 ~ 11:30Speaker
Jin-Yi Cai, University of Wisconsin – MadisonRoom
Room 102, School of Information Management & Engineering, Shanghai University of Finance & Economics
