Developments in Holographic Algorithms

COMPUTER SCIENCE DISCRETE MATH I
Topic:Developments in Holographic Algorithms
Speaker:Jin-Yi Cai
Affiliation:University of Wisconsin, Madison
Date:Monday, November 12
Time/Room:11:15am - 12:15pm/S-101

Valiant's theory of holographic algorithms is a new design method to produce polynomial time algorithms. 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 holographic algorithms.