Developments in Holographic Algorithms
Speaker: Jin-Yi Cai , U of Wisconsin-Madison, and Radcliffe Inst (Harvard U)
Date: February 19 2008
Time: 4:15PM to 5:30PM
Location: 32-G449 (Patil/Kiva)
Host: Madhu Sudan, MIT
Contact: Be Blackburn, 617 253-6098, imbe@mit.edu
Relevant URL: http://theory.csail.mit.edu/theory-seminars/calendar.html[note UNUSUAL LOCATION: 32-G449]
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.
See other events that are part of Theory Colloquium Spring 2008
See other events happening in February 2008
