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. All individuals must show the Daily Screener green pass in order to gain entry to the building.


How to Subscribe