The Hebrew University of Jerusalem Einstein Institute of Mathematics |
The Hebrew University of Jerusalem The Rachel and Selim Benin School of Computer Science & Engineering |
Prof. Subhash Khot (NYU)
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 |