Tag Archives: Muli Safra

Kelman, Kindler, Lifshitz, Minzer, and Safra: Towards the Entropy-Influence Conjecture

Posted on March 22, 2020 by

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 →

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

Tomorrow: Boolean functions day at the TAU theory fest

Posted on January 2, 2020 by

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 →

Posted in Combinatorics, Conferences, Convex polytopes | Tagged , , , , , , , | Leave a comment

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 , , , , , , , | 3 Comments

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 , , | 10 Comments

New Isoperimetric Results for Testing Monotonicity

Posted on April 21, 2015 by

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 , , | 4 Comments

Mittag-Leffler Institute and Yale, Winter 2005; Test your intuition: Who Played the Piano?

Posted on March 21, 2013 by

This is a little “flashback” intermission in my posts about my debate with Aram Harrow. This time I try to refer to Cris Moore’s question regarding  the motivation for my study. For the readers it gives an opportunity to win a … Continue reading →

Posted in Computer Science and Optimization, Controversies and debates, Physics, Test your intuition | Tagged , , , , , , , , , , , , , , , , , , , , , , , , | 11 Comments