Colloquium
"Developments in Holographic Algorithms"
Jin-Yi Cai, University of Wisconsin - Madison and Radcliffe Institute, Harvard University
Thursday, February 28, 2008 at 4:00 P.M.
Room 368 (CIT 3rd Floor)
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: John Savage
| Page Owner: Webmaster | Last Modified: Thu Jan 24 14:58:34 2008 |