Holographic Algorithms and Classification of Counting Problems

The P versus NP problem is one of the most challenging intellectual problems of our time. A fundamental goal of complexity theory is to provide classifications according to the inherent difficulty of computational problems. I will describe some recent advances in the study of counting problems. This includes Valiant's holographic algorithms and a number of complexity dichotomy theorems. In a holographic algorithm, information is represented in a superposition of linear vectors. 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. I will also describe a number of dichotomy theorems, for graph homomorphisms (spin systems), constraint satisfaction problems (CSP), and Holant problems. These dichotomies classify every problem in a class to be either computable in polynomial time or to be intractable. No background knowledge is required.

About the Speaker

Jin-Yi Cai studied at Fudan University in Shanghai, China (Class of 77). He received his Ph.D. in 1986 from Cornell University. He is currently the Steenbock Professor at the University of Wisconsin—Madison. His research interest is computational complexity theory. His awards include a Presidential Young Investigator award, Sloan and Guggenheim fellowships, and a Humboldt Research Award. He is a fellow of ACM (2001).

Event Topic

Distinguished Lecture Series