Theory Seminar: Agreement Testing and PCPs

Irit Dinur (​Weizmann Institute of Science)
Wednesday, 26.4.2017, 12:30
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.

Back to the index of events