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.
This video was produced by the Simons Institute, and forms part of the workshop Expanders and Extractors.
