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:

Refreshments will be offered starting 15 minutes prior to the scheduled start of the talk.


How to Subscribe