'''演讲人：蔡进一教授，威斯康星大学（麦迪逊）
时间：6 月 11 号下午 1:30pm ~~ 3:00pm
地点：张江校区二教 2107 教室
联系人：阚海斌，hbkan@fudan.edu.cn
Abstract:
The P versus NP problem is one of the most challenging intellectual problems of our time. A fundamental goal of computational complexity theory is to provide classifications according to the inherent difficulty of computational problems.
I will describe some recent advances in the study of Counting Problems. This includes Valiant's holographic algorithms, and a number of complexity dichotomy theorems.
In a holographic algorithm, information is represented in a superposition of linear vectors. This mixture creates the possibility for exponential sized cancellations of fragments of local computations. The underlying computation is done by invoking the Fisher-Kasteleyn-Temperley method for counting perfect matchings for planar graphs, which uses Pfaffians and runs in polynomial time. In this way some seemingly exponential time computations can be done in polynomial time. I will also describe a number of dichotomy theorems, for Graph Homomorphisms (spin systems), Constraint Satisfaction Problems (CSP), and Holant Problems. These dichotomies classify every problem in a class to be either computable in polynomial time, or to be intractable.
Bio:
Jin-Yi Cai studied at Fudan University (class of 77). He received his Ph.D. in 1986 from Cornell University.
He is currently the Steenbock Professor at the University of Wisconsin--Madison. His research interest is computational complexity theory. His awards include a PYI, a Sloan Fellowship, a Guggenheim Fellowship, and a Humboldt Research Award. He is a Fellow of ACM (2001).'''
