Eastern Great Lakes Theory Workshop Talk

From Alan Turing to Holographic Algorithms

Jin-Yi Cai, University of Wisconsin - Madison

Saturday, September 29, 4:00-5:00pm

ABSTRACT

From Turing we know there are uncomputable problems. Following Hartmanis and Sterns we know that there is a fine hierarchy of computable problems, some are more efficiently computable than others. A fundamental challenge of complexity theory is to prove classification theorems.

Valiant's theory of holographic algorithms is a new design method to produce polynomial time algorithms, particularly for counting type problems. 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 complexity classification theorems for counting problems, especially related to holographic algorithms.

Speaker Bio

Jin-Yi Cai received his Ph.D. from Cornell University in 1986. After faculty positions at Yale, Princeton, and SUNY Buffalo, he is currently a Professor at the University of Wisconsin--Madison. His area of research is computational complexity, where he has written and published over 100 research papers. Currently he is primarily working on dichotomy theorems for counting problems, such as counting constraint satisfaction problems (CSP). These dichotomy theorems classify all problems within a broad class. His awards include a Sloan Fellowship and a Guggenheim Fellowship. He was elected a Fellow of ACM in 2001.

< Schedule < EaGL-V homepage