Colloquium Details
2-to-2 Games is NP-hard
Speaker: Dor Minzer, Princeton University
Location: TBA
Date: March 23, 2020, 2 p.m.
Host: Michael Overton
Synopsis:
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
inequalities.
We will discuss the Unique Games Conjecture, this line of study, and
some of the ideas that go into the proof.
Speaker Bio:
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.
Notes:
In-person attendance only available to those with active NYU ID cards.