







This Week at Physics 

<< Spring 2015  Fall 2015  Spring 2016 >> 
Subscribe to receive email announcements of events 
Event Number 2740
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: JinYi 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 FisherKasteleynTemperley 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