You are here

Probabilistically Checkable Proofs: deducing a complicated global picture from very simple partial views

Friday, May 20, 2016 - 3:30pm
Kane 110
Lecture Poster: Probabilistically Checkable Proofs

Irit Dinur, The Weizmann Institute of Science (short biography)

Sometimes you just don't have enough time to read an entire proof, a brief scan is all you can afford. Probabilistically checkable proofs (PCPs), discovered 25 years ago, guarantee that even a brief scan will find an error if there is one. A PCP proof is created by taking a regular proof and splitting it cleverly into fragments. The key is a theorem asserting that locally consistent fragments must be coming from a globally correct proof. We will describe this surprising local-to-global phenomenon and show a variety of implications from computational optimization all the way to secure cloud computing.

Event Type: 
Event Subcalendar: 
Related Fields: