Recent Comments
Tag Archives: Muli Safra
Kelman, Kindler, Lifshitz, Minzer, and Safra: Towards the Entropy-Influence Conjecture
Let me briefly report on a remarkable new paper by Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, and Muli Safra, Revisiting Bourgain-Kalai and Fourier Entropies. The paper describes substantial progress towards the Entropy-Influence conjecture, posed by Ehud Friedgut and … Continue reading
Tomorrow: Boolean functions day at the TAU theory fest
As part of the 2019/2020 TAU theory fest, tomorrow, Friday, January 3, 2020, is a Boolean function day at Tel Aviv University. The five speakers are Esty Kelman, Noam Lifschitz, Renan Gross, Ohad Klein, and Naomi Kirshner. For more (and … Continue reading
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
