Type of Talk: UTCS Colloquium

Speaker Name

/Affiliation: Jin-Yi Cai/ Univ. of Wisconsin Madison and Radcliffe Instit

ute

Date: Wednesday November 7 2007 1:00p.m.

Location: A

CES 2.402

Host: David Zuckerman

Talk Title: Developments in
Holographic Algorithms

Talk Abstract:
Valiant''s theory of holog

raphic algorithms is a new design method to produce polynomial time algorit

hms. Information is represented in a superposition of linear vectors in a h

olographic mix. This mixture creates the possibility for
exponential si

zed cancellations of fragments of local computations. The underlying comput

ation is done by invoking the Fisher-Kasteleyn-Temperley
method for cou

nting 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 c

onception 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 h

olographic algorithms.