EECS Special Seminar: Dor Minzer, "2-to-2 Games is NP-hard"

SHARE:

Event Speaker: 

Dor Minzer

Event Location: 

Grier B 34-401

Event Date/Time: 

Monday, March 9, 2020 - 4:00pm

Research Area: 

The 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.
 

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.