2-to-2 Games is NP-hard
Speaker: Dor Minzer, Princeton University
Date: March 23, 2020, 2 p.m.
Host: Michael Overton
he Unique Games Conjecture, proposed by Khot in 2002, is a central open
problem in the study of probabalistically checkable proofs (PCP's),
which if true, would imply tight inapproximability results for wide
class of optimization problems. A recent line of study has proved a
related (but weaker) statement, known as the 2-to-2 Games Conjecture,
thereby giving strong evidence to the Unique Games Conjecture.
A central component in the proof of this conjecture is a
characterization of sets whose edge-expansion is bounded away from 1 in
the Grassmann Graph, a problem closely related to hypercontractive-type
We will discuss the Unique Games Conjecture, this line of study, and
some of the ideas that go into the proof.
Dor Minzer is a postdoctoral scholar in the Institute for Advanced
Study, Princeton. Prior to that, he received his Ph.D in 2018 from
Tel-Aviv University under the supervision of Prof. Muli Safra. His
research interests include complexity theory (particularly hardness of
approximation), analysis of Boolean functions and combinatorics.
Refreshments will be offered starting 15 minutes prior to the scheduled start of the talk.