BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:UW-Physics-TWaP
BEGIN:VEVENT
SEQUENCE:0
UID:UW-Physics-Event-2740
DTSTART:20120911T120500
DURATION:PT1H0M0S
LOCATION:4274 Chamberlin (refreshments will be served)
SUMMARY:Computational complexity theory -- The world of P and NP\, Chaos & Complex Systems Seminar\, Jin-Yi Cai\, UW Department of Computer Science
DESCRIPTION:Computational Complexity Theory is the study of intrinsic difficulties of computational problems. The most prominent open problem is the conjecture that P is not equal to NP.  In essense this conjecture states that it is intrinsically harder to find proofs than to verify them. It has a fundamental importance in many areas from computer science to mathematics\, to our basic understanding of nature.<br><br>
<br><br>
Valiant's new theory of holographic algorithms is one of the most beautiful ideas in algorithm design in recent memory.  It gives a new look on the P versus NP problem. In this theory\, information is represented by 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 (Dimer Problem). Holographic algorithms challenge our conception of what polynomial time computation can do\, in view of the P vs. NP question.<br><br>
<br><br>
In this talk we will survey the developments in holographic algorithms. No specialized background is assumed. 
URL:http://www.physics.wisc.edu/twap/view.php?id=2740
END:VEVENT
END:VCALENDAR