Local to Global, High Dimensional Expansion, and Probabilistically Checkable Proofs
27 March 2017 | Colloquium
ABSTRACT: 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. PCPs have a variety of implications, from hardness of computational optimization all the way to secure cloud computing. 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 relate this local to global phenomenon to a form of "high dimensional expansion", which is a relatively new notion in combinatorics. We will touch some directions that are opened up by this connection.
SHORT BIO: Irit Dinur is a professor of computer science at the Weizmann Institute of Science. She earned her doctorate in 2002 from Tel-Aviv University and spent her postdoc at IAS in Princeton and as a Miller fellow at UC Berkeley. Her research is in computational complexity, focusing on hardness of approximation and probabilistically checkable proofs, as well as combinatorics. 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 recipient of the 2007 Michael Bruno Memorial Award in Computer Science by Yad Hanadiv, the 2012 Anna and Lajos Erdős Prize in Mathematics, and was a plenary speaker at the 2010 International Congress of Mathematicians.
|Date||27 March 2017|
|Time||16:15 - 17:15|
|Speaker||Prof. Irit Dinur,|
|Area of expertise||Computer Sciences|