Wednesday, April 11, 2018 - 4:15pm to 5:15pm

Refreshments:

Light Refreshments at 4:00

Location:

STAR - D463

Speaker:

Dor Minzer, Tel Aviv University

Seminar group:

Abstract:

The PCP theorem characterizes the computational class NP,

so as to facilitate proofs that approximation problems are NP-hard.

It can be viewed as a significant strengthening of the famous Cook-Levin theorem,

stating that the problem of deciding the satisfiability of a given CNF formula is NP-complete.

It can be viewed as a significant strengthening of the famous Cook-Levin theorem,

stating that the problem of deciding the satisfiability of a given CNF formula is NP-complete.

A fundamental open question in PCP theory is whether a special type of PCP,

namely, 2-to-2-Games, is still NP-hard. This conjecture is a variant of Khot's well-known Unique-Games Conjecture.

namely, 2-to-2-Games, is still NP-hard. This conjecture is a variant of Khot's well-known Unique-Games Conjecture.

A recent line of study pursued a new attack on the 2-to-2 Games Conjecture (albeit with imperfect completeness).

The approach is based on a mathematical object called the Grassmann Graph, and relies on the study of edge-expansion in this graph.

More specifically, the study of sets of vertices in the Grassmann Graph that contain even a tiny fraction of the edges incident to the set.

More specifically, the study of sets of vertices in the Grassmann Graph that contain even a tiny fraction of the edges incident to the set.

A characterization of such sets was recently accomplished, completing a

proof for the 2-to-2 Games Conjecture (with imperfect completeness).

proof for the 2-to-2 Games Conjecture (with imperfect completeness).

The talk discusses the 2-to-2 Games Conjecture, its implications and the line of study.

Based on joint works with Irit Dinur, Subhash Khot, Guy Kindler and Muli Safra.