Upcoming Talks

Ist logo

Local to global, high-dimensional expansion, and probabilistically checkable proofs

Date: Monday, June 19, 2017 16:00 - 17:15
Speaker: Irit Dinur (Weizmann Institute of Technology)
Location: Raiffeisen Lecture Hall, Central Building
Series: Institute colloquium
Host: Uli Wagner
Contact: ELLER Arinya
Central building lecture hall

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 ​normal ​​ 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.
Recently, a connection was discovered between PCP “agreement tests” and a concept from combinatorial topology, so-called high-dimensional expanders. We will describe this connection and some future potential directions that it suggests.

Qr image
Download ICS Download invitation
Back to eventlist