September 3, 2009: Seminar - Jin-Yi Cai: "Computational Complexity Theory and Holographic Algorithms"

Seminar Announcement

Computational Complexity Theory and Holographic Algorithms

Jin-Yi Cai
Depatment of Computer Science
University of Wisconsin-Madison
Wednesday, September 16
1:30 p.m., SEO 1000


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 represents a totally original attack on the P and NP question. Alternatively it can be seen as a novel approach to study constrained satisfiability problem. In this theory, information is represented by 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 the developments in holographic algorithms. No specialized background is assumed.

Brief Bio:

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. 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.

Host: Professor Bhaskar DasGupta

Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF