Tag Archives: Muli Safra

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

Posted on March 22, 2020 by Gil Kalai

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 Gil Kalai

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 Gil Kalai

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 Gil Kalai

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 Gil Kalai

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 Gil Kalai

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