University of Wisconsin - Madison and Radcliffe Institute, Harvard University
Developments in Holographic Algorithms
Tuesday, February 19, 4:15pm
32-G449 Kiva (UNUSUAL location)
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 developments in holographic
algorithms.
Host: Ronitt Rubinfeld