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:20240328T151233Z
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.
\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