Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Agreement Testing and PCPs
event speaker icon
Irit Dinur (​Weizmann Institute of Science)
event date icon
Wednesday, 26.04.2017, 12:30
event location icon
Taub 201
I will describe the notion of agreement testing, which allows to deduce global structure from local agreement checks.

In retrospect, agreement testing theorems are a key combinatorial component in nearly all PCPs.

I will describe a couple of recent works. The first shows how an agreement testing theorem (which we don't yet know how to prove) would imply NP hardness for unique games with gap of 1/2-ε​ vs ε​. The second is a new agreement testing theorem on a sparse collection of sets, which implies a strong derandomization of direct products and sums.

Based on joint works with Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra; and with Tali Kaufman.