Talks
Spring 2017

High Dimensional Expanders and PCPs

Tuesday, January 31st, 2017 10:25 am11:10 am

Add to Calendar

I will describe a notion of high dimensional expansion called "agreement expansion", that can be described as a "sheaf cohomology". Agreement expansion captures certain PCP questions and in particular abstracts low degree tests such as plane vs. plane or line vs. line. 
I will then describe an agreement question on the finite-field Grassmannian which is a high dimensional version of the Raz-Safra plane vs. plane low degree test. We will discuss a hypothesis regarding agreement expansion on the Grassmannian. This hypothesis, if true, implies NP-hardness of 2:1 games, a variant of the unique games conjecture. 
 
Based on joint works with Tali Kaufman, Subhash Khot, Guy Kindler, Dor Mintzer, and Muli Safra.