Title: On the universality of the FKT algorithm
Abstract: I will describe our current work on the classification program on
Counting problems. These include most of Sum of product type
Computation, including spin systems, graph homomorphsism, constraint
Satisfaction problems. We discuss how universal the algorithm of
FKT for planar perfect matching, via holographic reductions,
Is for this program. I will describe a number of dichotomy theorems.
Time: 2:00-3:30 pm 28, June
Place: 研教楼320 （本部）
Jin-Yi Cai studied at Fudan University (class of 77).
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 and AAAS.
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.