Muli Safra

Publication Activity (10 Years)

Years Active: 2005-2023
Publications (10 Years): 19

Top Topics

Graph Embedding

Top Venues

Electron. Colloquium Comput. Complex.

Publications

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