Computer Science/Discrete Mathematics Seminar II
On the NP-hardness of 2-to-2 Games
The Unique-Games Conjecture is a central open problem in the field of PCP’s (Probabilistically Checkable Proofs) and hardness of approximation, implying tight inapproximability results for wide class of optimization problems.
We will discuss PCPs, the Unique-Games Conjecture and some recent progress. (no familiarity with PCPs or with last week's talk are needed).
Date & Time
October 30, 2018 | 10:30am – 12:30pm
Location
Simonyi Hall 101Speakers
Dor Minzer
Affiliation
Member, School of Mathematics