\n

\nValiant's new theory of holographic algorithms is one of the most beautiful ideas in algorithm design in recent memory. It gi ves a new look on the P versus NP problem. In this theory\, informatio n is represented by a superposition of linear vectors in a holographic mix. This mixture creates the possibility for exponential sized cance llations of fragments of local computations. The underlying computatio n is done by invoking the Fisher-Kasteleyn-Temperley method for counti ng perfect matchings for planar graphs (Dimer Problem). Holographic al gorithms challenge our conception of what polynomial time computation can do\, in view of the P vs. NP question.

\n

\nIn thi s talk we will survey the developments in holographic algorithms. No s pecialized background is assumed. URL:https://www.physics.wisc.edu/events/?id=2740 END:VEVENT END:VCALENDAR