BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:UW-Madison-Physics-Events
BEGIN:VEVENT
SEQUENCE:0
UID:UW-Physics-Event-2740
DTSTART:20120911T170500Z
DURATION:PT1H0M0S
DTSTAMP:20260420T035126Z
LAST-MODIFIED:20120829T195244Z
LOCATION:4274 Chamberlin (refreshments will be served)
SUMMARY:Computational complexity theory -- The world of P and NP\, Cha
 os & 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 proble
 m is the conjecture that P is not equal to NP.  In essense this conjec
 ture states that it is intrinsically harder to find proofs than to ver
 ify them. It has a fundamental importance in many areas from computer 
 science to mathematics\, to our basic understanding of nature.<br><br>
 
\n<br><br>
\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.<br><br>
\n<br><br>
\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