Classification Program for Counting Problems
- Prof. Jin-Yi Cai, University of Wisconsin-Madison
- Time: 2019-06-11 10:00
- Host: Prof. Xiaotie Deng
- Venue: Room 102, Courtyard No.5, Jingyuan
Abstract
Complexity Theory is the study of intrinsic difficulty of computational problems. One primary goal concerns with 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 asking whether a problem instance has a solution (the NP question), it asks how many solutions it has (the #P question). Many classical problems from statistical physics can also be formulated in this setting.
I will give a survey of the classification program for counting problems. They usually are 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.
Biography
Jin-Yi Cai studied at Fudan University. He continued his study at Temple University and at Cornell University, where he received his Ph. D. in 1986. He held faculty positions at Yale University (1986-1989), Princeton University (1989-1993), and SUNY Buffalo (1993-2000), rising from Assistant Professor to Full Professor in 1996. He is currently a Professor of Computer Science and Steenbock Professor of Mathematical Sciences at the University of Wisconsin--Madison.
He received a Presidential Young Investigator Award in 1990, an Alfred P. Sloan Fellowship in Computer Science in 1994, a John Simon Guggenheim Fellowship in 1998, and a Morningside Silver Medal of Mathematics in 2004. He also received the Humboldt Research Award for Senior U.S. Scientists. He has been elected a Fellow of ACM, AAAS, and a foreign member of Academia Europaea.
He is an Editor of Journal of Computer and Systems Sciences (JCSS), an Editor of International Journal of Foundations of Computer Science, an Associate Editor of Journal of Complexity, an Editor of The Chicago Journal of Theoretical Computer Science, and an Area Editor for International Journal of Software and Informatics. He works in computational complexity theory. He has written and published over 100 research papers.