The Taub Faculty of Computer Science Events and Talks
Irit Dinur (Weizmann Institute of Science)
Wednesday, 26.04.2017, 12:30
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.