Assaf Naor

Publication Activity (10 Years)

Years Active: 2002-2021
Publications (10 Years): 17

Top Topics

Approximate Nearest Neighbor

High Dimensional

Top Venues

Discret. Comput. Geom.

Publications

Vijay Bhattiprolu, Euiwoong Lee, Assaf Naor
A framework for quadratic form maximization over convex sets through nonconvex relaxations. STOC (2021)
Assaf Naor, Gilles Pisier, Gideon Schechtman
Impossibility of Dimension Reduction in the Nuclear Norm. Discret. Comput. Geom. 63 (2) (2020)
Subhash Khot, Assaf Naor
The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics. SODA (2019)
Ronen Eldan, Assaf Naor
Krivine diffusions attain the Goemans-Williamson approximation ratio. CoRR (2019)
Subhash Khot, Assaf Naor
The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics. CoRR (2018)
Assaf Naor, Gilles Pisier, Gideon Schechtman
Impossibility of dimension reduction in the nuclear norm. SODA (2018)
Assaf Naor
Metric dimension reduction: A snapshot of the Ribe program. CoRR (2018)
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Data-dependent hashing via nonlinear spectral gaps. STOC (2018)
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Hölder Homeomorphisms and Approximate Nearest Neighbors. FOCS (2018)
Assaf Naor, Robert Young
The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n. STOC (2017)
Assaf Naor
Probabilistic clustering of high dimensional norms. SODA (2017)
Assaf Naor, Gilles Pisier, Gideon Schechtman
Impossibility of dimension reduction in the nuclear norm. CoRR (2017)
Assaf Naor, Robert Young
Vertical perimeter versus horizontal perimeter. CoRR (2017)
Assaf Naor
A Spectral Gap Precludes Low-Dimensional Embeddings. SoCG (2017)
Assaf Naor, Robert Young
The integrality gap of the Goemans-Linial SDP relaxation for Sparsest Cut is at least a constant multiple of √log n. CoRR (2017)
Alexandr Andoni, Assaf Naor, Ofer Neiman
Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. ICALP (2016)
Assaf Naor
A spectral gap precludes low-dimensional embeddings. CoRR (2016)
Manor Mendel, Assaf Naor
Expanders with respect to Hadamard spaces and random graphs: extended abstract. ITCS (2014)
Assaf Naor, Oded Regev, Thomas Vidick
Efficient Rounding for the Noncommutative Grothendieck Inequality. Theory Comput. 10 (2014)
Assaf Naor
Every graph is essentially sparse. Commun. ACM 56 (8) (2013)
Assaf Naor, Oded Regev, Thomas Vidick
Efficient rounding for the noncommutative grothendieck inequality. STOC (2013)
Manor Mendel, Assaf Naor
Expanders with respect to Hadamard spaces and random graphs. CoRR (2013)
Steven Heilman, Aukosh Jagannath, Assaf Naor
. Discret. Comput. Geom. 50 (2) (2013)
Subhash Khot, Assaf Naor
Sharp kernel clustering algorithms and their associated Grothendieck inequalities. Random Struct. Algorithms 42 (3) (2013)
Jop Briët, Assaf Naor, Oded Regev
Locally decodable codes and the failure of cotype for projective tensor products CoRR (2012)
Steven Heilman, Aukosh Jagannath, Assaf Naor
. STOC (2012)
Assaf Naor, Oded Regev, Thomas Vidick
Efficient rounding for the noncommutative Grothendieck inequality CoRR (2012)
Assaf Naor
On the Banach-Space-Valued Azuma Inequality and Small-Set Isoperimetry of Alon-Roichman Graphs. Comb. Probab. Comput. 21 (4) (2012)
Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
The Grothendieck constant is strictly smaller than Krivine's bound. CoRR (2011)
Subhash Khot, Assaf Naor
Grothendieck-type inequalities in combinatorial optimization CoRR (2011)
Steven Heilman, Aukosh Jagannath, Assaf Naor
Solution of the propeller conjecture in $\R^3$ CoRR (2011)
Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, János Pach
Overlap properties of geometric expanders. SODA (2011)
Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor
The Grothendieck Constant is Strictly Smaller than Krivine's Bound. FOCS (2011)
Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, János Pach
Overlap properties of geometric expanders CoRR (2010)
Tim Austin, Assaf Naor, Alain Valette
The Euclidean Distortion of the Lamplighter Group. Discret. Comput. Geom. 44 (1) (2010)
Manor Mendel, Assaf Naor
Maximum gradient embeddings and monotone clustering. Comb. 30 (5) (2010)
Manor Mendel, Assaf Naor
Towards a Calculus for Non-Linear Spectral Gaps. SODA (2010)
Subhash Khot, Assaf Naor
Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities. SODA (2010)
Assaf Naor
L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry CoRR (2010)
William B. Johnson, Assaf Naor
The Johnson-Lindenstrauss Lemma Almost Characterizes Hilbert Space, But Not Quite. Discret. Comput. Geom. 43 (3) (2010)
Guy Kindler, Assaf Naor, Gideon Schechtman
Grothendieck Problem. Math. Oper. Res. 35 (2) (2010)
Subhash Khot, Assaf Naor
Sharp kernel clustering algorithms and their associated Grothendieck inequalities CoRR (2009)
Jeff Cheeger, Bruce Kleiner, Assaf Naor
A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP CoRR (2009)
William B. Johnson, Assaf Naor
The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite. SODA (2009)
Jeff Cheeger, Bruce Kleiner, Assaf Naor
CoRR (2009)
Jeff Cheeger, Bruce Kleiner, Assaf Naor
Integrality Gap for the Sparsest Cut SDP. FOCS (2009)
Subhash Khot, Assaf Naor
Approximate kernel clustering CoRR (2008)
Manor Mendel, Assaf Naor
Markov convexity and local rigidity of distorted metrics. SCG (2008)
Assaf Naor, Jacques Verstraëte
Parity check matrices and product representations of squares. Comb. 28 (2) (2008)
Subhash Khot, Assaf Naor
Diameter of Convex Bodies. SIAM J. Comput. 38 (4) (2008)
William B. Johnson, Assaf Naor
The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite CoRR (2008)
Subhash Khot, Assaf Naor
Approximate Kernel Clustering. FOCS (2008)
Guy Kindler, Assaf Naor, Gideon Schechtman
Grothendieck problem. SODA (2008)
Rajeev Motwani, Assaf Naor, Rina Panigrahy
Lower Bounds on Locality Sensitive Hashing. SIAM J. Discret. Math. 21 (4) (2007)
Subhash Khot, Assaf Naor
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. FOCS (2007)
Manor Mendel, Assaf Naor
Maximum Gradient Embeddings and Monotone Clustering. APPROX-RANDOM (2007)
Sanjeev Arora, James R. Lee, Assaf Naor
Fréchet Embeddings of Negative Type Metrics. Discret. Comput. Geom. 38 (4) (2007)
Piotr Indyk, Assaf Naor
Nearest-neighbor-preserving embeddings. ACM Trans. Algorithms 3 (3) (2007)
Assaf Naor, Gideon Schechtman
. SIAM J. Comput. 37 (3) (2007)
Dimitris Achlioptas, Assaf Naor, Yuval Peres
On the maximum satisfiability of random formulas. J. ACM 54 (2) (2007)
Manor Mendel, Assaf Naor
Ramsey partitions and proximity data structures. FOCS (2006)
Manor Mendel, Assaf Naor
Maximum gradient embeddings and monotone clustering CoRR (2006)
Noga Alon, Assaf Naor
Approximating the Cut-Norm via Grothendieck's Inequality. SIAM J. Comput. 35 (4) (2006)
Manor Mendel, Assaf Naor
Metric cotype. SODA (2006)
James R. Lee, Assaf Naor, Yuval Peres
Trees and Markov convexity. SODA (2006)
James R. Lee, Assaf Naor
Lp metrics on the Heisenberg group and the Goemans-Linial conjecture. FOCS (2006)
Assaf Naor, Gideon Schechtman
Planar Earthmover is not in L_1. FOCS (2006)
Rajeev Motwani, Assaf Naor, Rina Panigrahy
Lower bounds on locality sensitive hashing. SCG (2006)
Manor Mendel, Assaf Naor
Ramsey partitions and proximity data structures CoRR (2005)
Assaf Naor, Gideon Schechtman
CoRR (2005)
Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
Quadratic forms on graphs. STOC (2005)
Sanjeev Arora, James R. Lee, Assaf Naor
Euclidean distortion and the sparsest cut. STOC (2005)
Rajeev Motwani, Assaf Naor, Rina Panigrahy
Lower bounds on Locality Sensitive Hashing CoRR (2005)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Some Low Distortion Metric Ramsey Problems. Discret. Comput. Geom. 33 (1) (2005)
Assaf Naor, Jacques Verstraëte
Improved bounds on the size of sparse parity check matrices. ISIT (2005)
James R. Lee, Manor Mendel, Assaf Naor
: dimension, snowflakes, and average distortion. Eur. J. Comb. 26 (8) (2005)
Subhash Khot, Assaf Naor
Nonembeddability theorems via Fourier analysis. FOCS (2005)
Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor
Measured descent: A new embedding method for finite metrics CoRR (2004)
Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor
Measured Descent: A New Embedding Method for Finite Metrics. FOCS (2004)
Noga Alon, Assaf Naor
Approximating the cut-norm via Grothendieck's inequality. STOC (2004)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
Low dimensional embeddings of ultrametrics. Eur. J. Comb. 25 (1) (2004)
Dimitris Achlioptas, Assaf Naor
The two possible values of the chromatic number of a random graph. STOC (2004)
James R. Lee, Manor Mendel, Assaf Naor
Metric Structures in L1: Dimension, Snowflakes, and Average Distortion. LATIN (2004)
Dimitris Achlioptas, Assaf Naor, Yuval Peres
On the Maximum Satisfiability of Random Formulas. FOCS (2003)
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor
On metric ramsey-type phenomena. STOC (2003)
Ehud Friedgut, Gil Kalai, Assaf Naor
Boolean functions whose Fourier transform is concentrated on the first two levels. Adv. Appl. Math. 29 (3) (2002)
Nathan Linial, Avner Magen, Assaf Naor
Girth and euclidean distortion. STOC (2002)