Dear students,
Friday, May 20, 2016, 3:30 PM
Irit Dinur
The Weizmann Institute of Science
Probabilistically Checkable Proofs: deducing a complicated global picture from very simple partial views
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.
Speaker Bio:
Irit Dinur is a professor of computer science at the Weizmann Institute of Science. Her research is in computational complexity. She earned her doctorate in 2002 from Tel-Aviv University. In 2006 she discovered a new proof of the PCP theorem that was significantly simpler than previous proofs of the same result. She is the recepient of the 2007 Michael Bruno Memorial Award in Computer Science by Yad Hanadiv. She was a plenary speaker at the 2010 International Congress of Mathematicians. In 2012, she won the Anna and Lajos Erdős Prize in Mathematics.