The Hebrew University of Jerusalem
Einstein Institute of Mathematics
Hebrew University of Jerusalem The Hebrew University of Jerusalem
The Rachel and Selim Benin School of Computer Science & Engineering

Center for Theoretical Computer Science and Discrete Mathematics


Erdős Lectures in Discrete Mathematics and Theoretical Computer Science

May 18th, 20th-21st 2015

Prof. Subhash Khot    (NYU)

The lectures will be held at the Edmond Safra Campus    Givat Ram, Jerusalem

First talk:    Monday, May 18th, 2015, 10:30am    Rothberg building(s), Room B220

On Monotonicity Testing and Boolean Isoperimetric type Theorems


The talk presents a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, one obtains a monotonicity testing algorithm that makes n^{1/2} non-adaptive queries to a function f:{0,1}^n -> {0,1}, always accepts a monotone function and rejects a function that is far from being monotone with constant probability.

Joint work with Dor Minzer and Muli Safra.


Paper

Second talk:    Wednesday, May 20th, 2015, 10:30am    Rothberg building(s), Room B221

Candidate Lasserre Integrality Gap For Unique Games


In recent years, an algorithm based on Lasserre semidefinite programming relaxation has been proposed towards efficiently solving the Unique Games problem. If the algorithm works, it would yield a disproval of the Unique Games Conjecture. On the other hand, constructing an integrality gap instance for the relaxation would indicate that the algorithm does not work.

In the speaker's opinion, the existence of integrality gap for the Lasserre relaxation is the most pressing question in approximability. The Lasserre relaxation has a dual view as a Sum-of-Squares proof system and the integrality gap for the former corresponds to a degree lower bound for the latter.

The talk proposes a candidate Lasserre integrality gap construction for the Unique Games problem. Specifically, a concrete instance of the Unique Games problem is constructed. The instance is shown to have a good SDP solution. The authors believe that the instance does not have a good integral solution, but are unable to prove so.

The construction is based on a suggestion in [K Moshkovitz, STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution of the Unique Games Conjecture.

Joint work with Dana Moshkovitz.


Write-up

Third talk:    Thursday, May 21, 2015, 12:00pm    Mathematics Building, Lecture Hall 2

Hardness of Approximation


This talk sketches some connections between approximability of NP-complete problems, analysis and geometry, and the role played by the Unique Games Conjecture in facilitating these connections.
Accompanying article


Comments to: N. Levin, email: naavah at math.huji.ac.il
Design, construction & editing: N. Levin
Last updated: May 14th, 2015