The Taub Faculty of Computer Science Events and Talks

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.