Assaf Naor - RankMe

92 papers A* 37A 1B 2Journal 49Unranked 3

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