דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Agreement Testing and PCPs
event speaker icon
אירית דינור (מכון ויצמן למדע)
event date icon
יום רביעי, 26.4.2017, 12:30
event location icon
טאוב 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.
[בחזרה לאינדקס האירועים]