Tag Archives: Subhash Khot

Hardness of Approximating Vertex Cover, Polytope-Integrality-Gap, the Alswede-Kachatrian theorem, and More.

Posted on January 21, 2018 by

Lior Silberman asked about applications of the 2-to-2 game theorem to hardness of approximation, and James Lee answered mentioning applications to vertex cover. Let me elaborate a little on vertex cover, and other matters. (Here is the pervious post on … Continue reading →

Posted in Combinatorics, Computer Science and Optimization | Tagged , , , , , , , | 1 Comment

Subhash Khot, Dor Minzer and Muli Safra completed the proof of the 2-to-2 Games Conjecture

Posted on January 10, 2018 by

Update: A related blog post by Boaz Barak: Unique Games Conjecture – halfway there? The 2-to-2 Games Conjecture is a somewhat weaker form of Khot’s unique game conjecture. The paper is: Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion by Subhash Khot, Dor … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , , | 8 Comments

Media Item from “Haaretz” Today: “For the first time ever…”

Posted on August 13, 2014 by

Maryam Mirzakhani received the medal from South Korea’s president Park Geun-hye.  Here is an article from today’s Israeli newspaper Haaretz.  It is based on this article by the Guardian (Thanks, Manor!).  See also this post on Laba’s accidental mathematician and John Baez’ … Continue reading →

Posted in Conferences, Updates, Women in science | Tagged , , , , , , , , | 2 Comments