"Developments in Holographic Algorithms"

Jin-Yi Cai, University of Wisconsin - Madison and Radcliffe Institute, Harvard University

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.