Abstract
The 2-to-2 conjecture is the less-well-known sibling of the Unique-Games conjecture of Khot, with the latter one having extremely strong implications for PCP and approximation algorithms. One advantage of the first conjecture, however, is that it has recently been positively resolved.
The 2-to-2 conjecture still implies some in-approximability results, and it also indicates that current approaches towards disproving the Unique-Games conjecture would not work. But it is also interesting in terms of the technical tools used in the proof: The result makes use of a new notion of weak-decoding of a codeword, much weaker than list decoding. This notion, and its analysis, might prove useful in the context of PCP and in other parts of mathematics. In very high-level, it shows that a codeword that passes a test with non-negligible probability cannot be "pseudo-random". More concretely, it shows that non-expanding sets in the Grassmann graph must contain some specific nice subsets.
In the talks I'll describe the results and the techniques that went into the proof of the 2-to-2 conjecture, and some recent simplifications and generalizations.
Joint work with Irit Dinur, Subhash Khot, Dor Minzer, and Muli Safra, and with Noam Lifshitz, and David Ellis.