Robert Stewart Distinguished Lecture Series by Dr. Jin-Yi Cai

10 Apr, 2008


Time: 3:40PM
Location:1210 LeBaron
Title:Computational Complexity and Holographic Algorithms

Abstract: The most central open problem in Theoretical Computer Science is the P versus NP problem. It is widely conjectured that P is not equal to NP, but so far no proof is in sight.Recently Valiant introduced holographic algorithms, a new design method to perform polynomial time computations. Information is represented in a superposition of linear vectors in a holographic mix. 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, and some minor variations of the problems are known to be NP-hard or #P-hard. Holographic algorithms challenge our conception of what polynomial time computations can do, in view of the P vs. NP question.

In this talk we will survey some new developments in holographic algorithms. No specialized knowledge of computational complexity theory is assumed.




About the Speaker :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 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 Associate Editor of Journal of Complexity, Journal of Computer and Systems Sciences (JCSS), an Editor of International Journal of Foundations of Computer Science, an Editor of The Chicago Journal of Theoretical Computer Science and a member of the Scientific Board for the Electronic Colloquium on Computational Complexity. He works in computational complexity theory. He has written and published over 100 research papers. His recent paper with Pinyan Lu on holographic algorithms won the best paper award at ICALP 2007.