CIS Colloquium, Nov 20, 2008, 03:00PM – 04:00PM, Kiva Auditorium
Computational Complexity Theory and Holographic Algorithms
Dr. Jin-Yi Cai, University of Wisconsin, Madison
Computational Complexity Theory is the study of intrinsic difficulties of computational problems. The most prominent open problem is the conjecture that P is not equal to NP. In essense this conjecture states that it is intrinsically harder to find proofs than to verify them. It has a fundamental importance in many areas of computer science, from computer security to our basic understanding of the nature of efficient computation.
Valiant’s new theory of holographic algorithms is one of the most beautiful ideas in algorithm design in recent memory. It is a novel and striking example of an unintuitive algorithm design paradign that achieves polynomial time computation. Alternatively it can be seen as a powerful approach to the study of constrained satisfiability problem, and hardness reductions. In this theory, information is represented by a superposition in a suitable tensor product space, as a holographic mix, somewhat analogous to quantum algorithms (but no quantum device is needed). 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 developments in holographic algorithms. No specialized background is assumed.
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 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.