Lecture notes on DKKMS

Mitali Bafna, Chi-Ning Chou, and Zhao Song wrote scribe notes for my lectures on the Dinur et al proof of the 2 to 2 conjecture (see the DKKMS  and KMS papers, though this presentation follows a different, and in my view simpler, approach.)

“Scribe notes” is really an understatement. In a heroic work, Mitali, Chi-Ning and Zhao supplied many more details and proofs (and much better exposition, including figures and comments) than I actually did in my talks.  (One proof is still missing, but hopefully it will be updated in a few weeks or so.)

The notes assume no background in prior works on PCP and unique games, and can be very useful for anyone interested in these recent breakthroughs. As I mentioned before, the reduction itself can be described in about 5 lines. The soundness analysis is unfortunately more complicated…

5 thoughts on “Lecture notes on DKKMS

  1. This is going to look pedantic and nitpickey, but is there any way to have a version with the {fullpage} package? Large margins make it much harder to read, I feel.

Comments are closed.