Tutorial on 2-to-1 and Unique Games

Tutorial on 2-to-1 and Unique Games

Organized by Irit Dinur, Guy Kindler, and Dor Minzer

Saturday, October 6th, Institut Henri Poincaré (Paris), FOCS 2018 Workshop & Tutorials day

14:00-17:45

Lecture 1 (14:00-15:00): Irit Dinur

Background on unique games conjecture, the new 2:1 result and implications, high level description of the construction, highlighting "subcode covering"

Coffee break (15:00-15:30)

Lecture 2 (15:30-16:30): Guy Kindler

The Grassmann encoding, graph, and test, and its subtle soundness analysis. This includes the reduction from the test to the structure of non-expanding sets.

Lecture 3 (16:45-17:45): Dor Minzer

Non-expanding sets in the Grassman graph and proof of the soundness conjecture via harmonic analysis