Muli Safra

36 papers A* 11A 4Journal 20Unranked 1
YearRankTypeTitle / Venue / Authors
2025 J jnl
Deterministic Hardness of Approximation of Unique-SVP and GapSVP in ℓ
CoRR
Yahli Hecht, Muli Safra
2025 J jnl
Small Set Expansion in the Johnson Graph.
Theory Comput.
Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra
2023 A conf
NP-Hardness of Almost Coloring Almost 3-Colorable Graphs.
APPROX/RANDOM
Yahli Hecht, Dor Minzer, Muli Safra
2023 J jnl
On the Shortest Lattice Vector vs. the Shortest Basis.
CoRR
Yael Eisenberg, Itamar Rot, Muli Safra
2021 A conf
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.
ITCS
Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2020 J jnl
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.
Electron. Colloquium Comput. Complex.
Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2020 A* conf
Towards a Proof of the Fourier-Entropy Conjecture?
FOCS
Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, Muli Safra
2019 J jnl
Revisiting Bourgain-Kalai and Fourier Entropies.
CoRR
Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, Muli Safra
2018 J jnl
On Monotonicity Testing and Boolean Isoperimetric-type Theorems.
SIAM J. Comput.
Subhash Khot, Dor Minzer, Muli Safra
2018 A* conf
On non-optimally expanding sets in Grassmann graphs.
STOC
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2018 A* conf
Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion.
FOCS
Subhash Khot, Dor Minzer, Muli Safra
2018 J jnl
Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion.
Electron. Colloquium Comput. Complex.
Subhash Khot, Dor Minzer, Muli Safra
2018 J jnl
Small Set Expansion in The Johnson Graph.
Electron. Colloquium Comput. Complex.
Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra
2018 A* conf
Towards a proof of the 2-to-1 games conjecture?
STOC
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2017 J jnl
On Non-Optimally Expanding Sets in Grassmann Graphs.
Electron. Colloquium Comput. Complex.
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2017 A* conf
On independent sets, 2-to-2 games, and Grassmann graphs.
STOC
Subhash Khot, Dor Minzer, Muli Safra
2016 J jnl
On Independent Sets, 2-to-2 Games and Grassmann Graphs.
Electron. Colloquium Comput. Complex.
Subhash Khot, Dor Minzer, Muli Safra
2016 J jnl
Towards a Proof of the 2-to-1 Games Conjecture?
Electron. Colloquium Comput. Complex.
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
2015 A* conf
On Monotonicity Testing and Boolean Isoperimetric Type Theorems.
FOCS
Subhash Khot, Dor Minzer, Muli Safra
2015 J jnl
On Monotonicity Testing and Boolean Isoperimetric type Theorems.
Electron. Colloquium Comput. Complex.
Subhash Khot, Dor Minzer, Muli Safra
2015 J jnl
On the Converse of Talagrand's Influence Inequality.
CoRR
Saleet Klein, Amit Levi, Muli Safra, Clara Shikhelman, Yinon Spinka
2013 J jnl
A Two-Prover One-Round Game with Strong Soundness.
Theory Comput.
Subhash Khot, Muli Safra
2013 A conf
Towards an optimal query efficient PCP?
ITCS
Subhash Khot, Muli Safra, Madhur Tulsiani
2012 J jnl
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.
ACM Trans. Comput. Theory
Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, Omri Weinstein
2012 J jnl
Towards An Optimal Query Efficient PCP?
Electron. Colloquium Comput. Complex.
Subhash Khot, Muli Safra, Madhur Tulsiani
2011 A* conf
A Two Prover One Round Game with Strong Soundness.
FOCS
Subhash Khot, Muli Safra
2011 — conf
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.
APPROX-RANDOM
Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein
2011 J jnl
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity
CoRR
Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein
2011 J jnl
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
Theory Comput.
Per Austrin, Subhash Khot, Muli Safra
2010 A* conf
Hardness of Finding Independent Sets in Almost 3-Colorable Graphs.
FOCS
Irit Dinur, Subhash Khot, Will Perkins, Muli Safra
2009 A conf
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
CCC
Per Austrin, Subhash Khot, Muli Safra
2008 A* conf
Ranged hash functions and the price of churn.
SODA
James Aspnes, Muli Safra, Yitong Yin
2007 A* conf
Hardness Amplification for Errorless Heuristics.
FOCS
Andrej Bogdanov, Muli Safra
2007 J jnl
Hardness amplification for errorless heuristics.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Muli Safra
2005 J jnl
On Non-Approximability for Quadratic Programs
Electron. Colloquium Comput. Complex.
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra
2005 A* conf
On Non-Approximability for Quadratic Programs.
FOCS
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra