Recent Comments
-
Recent Posts
- What is mathematics (or at least, how it feels)
- Alef’s Corner
- To cheer you up in difficult times 22: some mathematical news! (Part 1)
- Cheerful News in Difficult Times: The Abel Prize is Awarded to László Lovász and Avi Wigderson
- Amazing: Feng Pan and Pan Zhang Announced a Way to “Spoof” (Classically Simulate) the Google’s Quantum Supremacy Circuit!
- To cheer you up in difficult times 21: Giles Gardam lecture and new result on Kaplansky’s conjectures
- Nostalgia corner: John Riordan’s referee report of my first paper
- At the Movies III: Picture a Scientist
- At the Movies II: Kobi Mizrahi’s short movie White Eye makes it to the Oscar’s short list.
Top Posts & Pages
- To cheer you up in difficult times 21: Giles Gardam lecture and new result on Kaplansky's conjectures
- To cheer you up in difficult times 5: A New Elementary Proof of the Prime Number Theorem by Florian K. Richter
- Amazing: Simpler and more general proofs for the g-theorem by Stavros Argyrios Papadakis and Vasiliki Petrotou, and by Karim Adiprasito, Stavros Argyrios Papadakis, and Vasiliki Petrotou.
- Are Natural Mathematical Problems Bad Problems?
- Cheerful News in Difficult Times: The Abel Prize is Awarded to László Lovász and Avi Wigderson
- The Argument Against Quantum Computers - A Very Short Introduction
- What is mathematics (or at least, how it feels)
- TYI 30: Expected number of Dice throws
- To cheer you up in difficult times 17: Amazing! The Erdős-Faber-Lovász conjecture (for large n) was proved by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus!
RSS
Tag Archives: Subhash Khot
Hardness of Approximating Vertex Cover, Polytope-Integrality-Gap, the Alswede-Kachatrian theorem, and More.
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
Subhash Khot, Dor Minzer and Muli Safra completed the proof of the 2-to-2 Games Conjecture
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 Dor Minzer, Muli Safra, Subhash Khot
10 Comments
New Isoperimetric Results for Testing Monotonicity
Muli, Dor and Subash, Jerusalem May 21 2015. Michel Talagrand Gregory Margulis Property testing In this post I will tell you about a new paper by Subhash Khot, Dor Minzer and Muli Safra entitled: On … Continue reading
Posted in Combinatorics, Computer Science and Optimization
Tagged Dor Minser, Muli Safra, Subhash Khot
4 Comments
Media Item from “Haaretz” Today: “For the first time ever…”
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