<< September 2012 >>
 
 >>
 >>
 >>
 >>
 >>
 >>
Sun Mon Tue Wed Thu Fri Sat
   1 
 2   3   4   5   6   7   8 
 9   10   11   12   13   14   15 
 16   17   18   19   20   21   22 
 23   24   25   26   27   28   29 
 30   
 
Add an Event

This Week at Physics

<< Spring 2012 Fall 2012 Spring 2013 >>

Events on Tuesday, September 11th, 2012

Chaos & Complex Systems Seminar
Computational complexity theory -- The world of P and NP
Time: 12:05 pm
Place: 4274 Chamberlin (refreshments will be served)
Speaker: Jin-Yi Cai, UW Department of Computer Science
Abstract: 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>
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>
In this talk we will survey the developments in holographic algorithms. No specialized background is assumed.
Host: Sprott
Add this event to your calendar

©2013 Board of Regents of the University of Wisconsin System