Assaf Naor

According to our database, Assaf Naor authored at least 63 papers between 2002 and 2021.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2021

A framework for quadratic form maximization over convex sets through nonconvex relaxations.

Vijay Bhattiprolu, Euiwoong Lee, Assaf Naor

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

Impossibility of Dimension Reduction in the Nuclear Norm.

Assaf Naor, Gilles Pisier, Gideon Schechtman

Discret. Comput. Geom., 2020

2019

Krivine diffusions attain the Goemans-Williamson approximation ratio.

Ronen Eldan, Assaf Naor

CoRR, 2019

The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics.

Subhash Khot, Assaf Naor

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Metric dimension reduction: A snapshot of the Ribe program.

Assaf Naor

CoRR, 2018

Data-dependent hashing via nonlinear spectral gaps.

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Hölder Homeomorphisms and Approximate Nearest Neighbors.

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Vertical perimeter versus horizontal perimeter.

Assaf Naor, Robert Young

CoRR, 2017

The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n.

Assaf Naor, Robert Young

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Probabilistic clustering of high dimensional norms.

Assaf Naor

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

A Spectral Gap Precludes Low-Dimensional Embeddings.

Assaf Naor

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016

Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost.

Alexandr Andoni, Assaf Naor, Ofer Neiman

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2014

Efficient Rounding for the Noncommutative Grothendieck Inequality.

Assaf Naor, Oded Regev, Thomas Vidick

Theory Comput., 2014

Expanders with respect to Hadamard spaces and random graphs: extended abstract.

Manor Mendel, Assaf Naor

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

Sharp kernel clustering algorithms and their associated Grothendieck inequalities.

Subhash Khot, Assaf Naor

Random Struct. Algorithms, 2013

Solution of the Propeller Conjecture in ℝ³.

Steven Heilman, Aukosh Jagannath, Assaf Naor

Discret. Comput. Geom., 2013

Expanders with respect to Hadamard spaces and random graphs.

Manor Mendel, Assaf Naor

CoRR, 2013

Every graph is essentially sparse.

Assaf Naor

Commun. ACM, 2013

2012

On the Banach-Space-Valued Azuma Inequality and Small-Set Isoperimetry of Alon-Roichman Graphs.

Assaf Naor

Comb. Probab. Comput., 2012

Locally decodable codes and the failure of cotype for projective tensor products

Jop Briët, Assaf Naor, Oded Regev

CoRR, 2012

2011

Solution of the propeller conjecture in $\R^3$

Steven Heilman, Aukosh Jagannath, Assaf Naor

CoRR, 2011

Grothendieck-type inequalities in combinatorial optimization

Subhash Khot, Assaf Naor

CoRR, 2011

Overlap properties of geometric expanders.

Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, János Pach

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The Grothendieck Constant is Strictly Smaller than Krivine's Bound.

Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

The UGC Hardness Threshold of the <i>L_p</i> Grothendieck Problem.

Guy Kindler, Assaf Naor, Gideon Schechtman

Math. Oper. Res., 2010

The Johnson-Lindenstrauss Lemma Almost Characterizes Hilbert Space, But Not Quite.

William B. Johnson, Assaf Naor

Discret. Comput. Geom., 2010

The Euclidean Distortion of the Lamplighter Group.

Tim Austin, Assaf Naor, Alain Valette

Discret. Comput. Geom., 2010

L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry

Assaf Naor

CoRR, 2010

Maximum gradient embeddings and monotone clustering.

Manor Mendel, Assaf Naor

Comb., 2010

Towards a Calculus for Non-Linear Spectral Gaps.

Manor Mendel, Assaf Naor

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

Compression bounds for Lipschitz maps from the Heisenberg group to L₁

Jeff Cheeger, Bruce Kleiner, Assaf Naor

CoRR, 2009

A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP

Jeff Cheeger, Bruce Kleiner, Assaf Naor

CoRR, 2009

A (log n)^Omega(1) Integrality Gap for the Sparsest Cut SDP.

Jeff Cheeger, Bruce Kleiner, Assaf Naor

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

Linear Equations Modulo 2 and the L₁ Diameter of Convex Bodies.

Subhash Khot, Assaf Naor

SIAM J. Comput., 2008

Parity check matrices and product representations of squares.

Assaf Naor, Jacques Verstraëte

Comb., 2008

The UGC hardness threshold of the ℓ_<i>p</i> Grothendieck problem.

Guy Kindler, Assaf Naor, Gideon Schechtman

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Approximate Kernel Clustering.

Subhash Khot, Assaf Naor

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Markov convexity and local rigidity of distorted metrics.

Manor Mendel, Assaf Naor

Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007

Nearest-neighbor-preserving embeddings.

Piotr Indyk, Assaf Naor

ACM Trans. Algorithms, 2007

Lower Bounds on Locality Sensitive Hashing.

Rajeev Motwani, Assaf Naor, Rina Panigrahy

SIAM J. Discret. Math., 2007

Planar Earthmover Is Not in L₁.

Assaf Naor, Gideon Schechtman

SIAM J. Comput., 2007

On the maximum satisfiability of random formulas.

Dimitris Achlioptas, Assaf Naor, Yuval Peres

J. ACM, 2007

Fréchet Embeddings of Negative Type Metrics.

Sanjeev Arora, James R. Lee, Assaf Naor

Discret. Comput. Geom., 2007

Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies.

Subhash Khot, Assaf Naor

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Approximating the Cut-Norm via Grothendieck's Inequality.

Noga Alon, Assaf Naor

SIAM J. Comput., 2006

Metric cotype.

Manor Mendel, Assaf Naor

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Trees and Markov convexity.

James R. Lee, Assaf Naor, Yuval Peres

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Planar Earthmover is not in L_1.

Assaf Naor, Gideon Schechtman

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Ramsey partitions and proximity data structures.

Manor Mendel, Assaf Naor

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Lp metrics on the Heisenberg group and the Goemans-Linial conjecture.

James R. Lee, Assaf Naor

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Metric structures in <i>L</i>₁: dimension, snowflakes, and average distortion.

James R. Lee, Manor Mendel, Assaf Naor

Eur. J. Comb., 2005

Some Low Distortion Metric Ramsey Problems.

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

Discret. Comput. Geom., 2005

Euclidean distortion and the sparsest cut.

Sanjeev Arora, James R. Lee, Assaf Naor

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Quadratic forms on graphs.

Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Improved bounds on the size of sparse parity check matrices.

Assaf Naor, Jacques Verstraëte

Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005

Nonembeddability theorems via Fourier analysis.

Subhash Khot, Assaf Naor

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Low dimensional embeddings of ultrametrics.

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

Eur. J. Comb., 2004

The two possible values of the chromatic number of a random graph.

Dimitris Achlioptas, Assaf Naor

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Metric Structures in L1: Dimension, Snowflakes, and Average Distortion.

James R. Lee, Manor Mendel, Assaf Naor

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Measured Descent: A New Embedding Method for Finite Metrics.

Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

On metric ramsey-type phenomena.

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

Boolean functions whose Fourier transform is concentrated on the first two levels.

Ehud Friedgut, Gil Kalai, Assaf Naor

Adv. Appl. Math., 2002

Girth and euclidean distortion.

Nathan Linial, Avner Magen, Assaf Naor

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002