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,
Language English
Area of expertise Computer Sciences
Host Dep. Informatik
Include this event in your calendar (ICS, 5kB) 
Page URL: https://www.inf.ethz.ch/news-and-events/events/event-detail.html
Fri Jul 28 20:48:36 CEST 2017
© 2017 Eidgenössische Technische Hochschule Zürich