Robert Stewart Distinguished Lecture Series by Dr. Jin-Yi Cai
10 Apr, 2008 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.
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.
|
