Recent Comments
-
Recent Posts
- Some News from a Seminar in Cambridge
- Subspace Designs, Unit and Distinct Distances, and Piercing Standard Boxes.
- Greg Kuperberg @ Tel Aviv University
- Israel AGT Day, Reichman University, March 5, 2023
- Alef’s Corner: Democracy (Israel, 2023)
- Absolutely Sensational Morning News – Zander Kelley and Raghu Meka proved Behrend-type bounds for 3APs
- The Trifference Problem
- Greatest Hits 2015-2022, Part II
- Greatest Hits 2015-2022, Part I
Top Posts & Pages
- Some News from a Seminar in Cambridge
- Absolutely Sensational Morning News - Zander Kelley and Raghu Meka proved Behrend-type bounds for 3APs
- Greg Kuperberg @ Tel Aviv University
- Quantum Computers: A Brief Assessment of Progress in the Past Decade
- To cheer you up in difficult times 7: Bloom and Sisask just broke the logarithm barrier for Roth's theorem!
- 'Gina Says'
- Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
- R(5,5) ≤ 48
- The Argument Against Quantum Computers - A Very Short Introduction
RSS
Tag Archives: Muli Safra
Tel Aviv University Theory Fest is Starting Tomorrow
Tel Aviv University Theory Fest, December 26-December 28 2022. Cryptography workshop @ TAU TheoryFest December 29, 2022 TAU 2022 TheoryFest, December 26-28, 2022 The Theory of Computing was born as a purely mathematical investigation into the notion of computation. From … Continue reading
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
Posted in Combinatorics, Computer Science and Optimization, Open problems
Tagged Dor Minzer, Esty Kelman, Guy Kindler, Muli Safra, Noam Lifshitz
2 Comments
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
11 Comments
New Isoperimetric Results for Testing Monotonicity
Muli, Dor and Subhash, 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
5 Comments