Skip to content

Lecture notes on DKKMS

April 15, 2018

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 Comments
  1. April 15, 2018 5:20 am

    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.

  2. April 18, 2018 8:39 pm

    Updated with fullpage and also some citations to KMS1,DKKMS2 as well as notes as to what proofs are missing.

Trackbacks

  1. Unique Games Conjecture – halfway there? | Windows On Theory

Comments are closed.

%d bloggers like this: