| 2026 | SODA | An optimal algorithm for average distance in typical regular graphs. | Alexandros Eskenazis, Manor Mendel, Assaf Naor |
| 2026 | SODA | Optimal randomized clustering for subsets of L | Assaf Naor, Kevin Ren |
| 2025 | STOC | Optimal Rounding for Sparsest Cut. | Alan Chang, Assaf Naor, Kevin Ren |
| 2021 | STOC | A framework for quadratic form maximization over convex sets through nonconvex relaxations. | Vijay Bhattiprolu, Euiwoong Lee, Assaf Naor |
| 2019 | SODA | The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics. | Subhash Khot, Assaf Naor |
| 2018 | FOCS | Hlder Homeomorphisms and Approximate Nearest Neighbors. | Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
| 2018 | SODA | Impossibility of dimension reduction in the nuclear norm. | Assaf Naor, Gilles Pisier, Gideon Schechtman |
| 2018 | STOC | Data-dependent hashing via nonlinear spectral gaps. | Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
| 2017 | SODA | Probabilistic clustering of high dimensional norms. | Assaf Naor |
| 2017 | STOC | 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 |
| 2016 | ICALP | Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. | Alexandr Andoni, Assaf Naor, Ofer Neiman |
| 2013 | STOC | Efficient rounding for the noncommutative grothendieck inequality. | Assaf Naor, Oded Regev, Thomas Vidick |
| 2012 | STOC | Solution of the propeller conjecture in R | Steven Heilman, Aukosh Jagannath, Assaf Naor |
| 2011 | FOCS | The Grothendieck Constant is Strictly Smaller than Krivine's Bound. | Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor |
| 2011 | SODA | Overlap properties of geometric expanders. | Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, Jnos Pach |
| 2010 | SODA | Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities. | Subhash Khot, Assaf Naor |
| 2010 | SODA | Towards a Calculus for Non-Linear Spectral Gaps. | Manor Mendel, Assaf Naor |
| 2009 | FOCS | A (log n) | Jeff Cheeger, Bruce Kleiner, Assaf Naor |
| 2009 | SODA | The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite. | William B. Johnson, Assaf Naor |
| 2008 | FOCS | Approximate Kernel Clustering. | Subhash Khot, Assaf Naor |
| 2008 | SODA | The UGC hardness threshold of the ℓ | Guy Kindler, Assaf Naor, Gideon Schechtman |
| 2007 | FOCS | Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. | Subhash Khot, Assaf Naor |
| 2006 | FOCS | Lp metrics on the Heisenberg group and the Goemans-Linial conjecture. | James R. Lee, Assaf Naor |
| 2006 | FOCS | Ramsey partitions and proximity data structures. | Manor Mendel, Assaf Naor |
| 2006 | FOCS | Planar Earthmover is not in L_1. | Assaf Naor, Gideon Schechtman |
| 2006 | SODA | Trees and Markov convexity. | James R. Lee, Assaf Naor, Yuval Peres |
| 2006 | SODA | Metric cotype. | Manor Mendel, Assaf Naor |
| 2005 | FOCS | Nonembeddability theorems via Fourier analysis. | Subhash Khot, Assaf Naor |
| 2005 | ISIT | Improved bounds on the size of sparse parity check matrices. | Assaf Naor, Jacques Verstrate |
| 2005 | STOC | Quadratic forms on graphs. | Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor |
| 2005 | STOC | Euclidean distortion and the sparsest cut. | Sanjeev Arora, James R. Lee, Assaf Naor |
| 2004 | FOCS | Measured Descent: A New Embedding Method for Finite Metrics. | Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor |
| 2004 | LATIN | Metric Structures in L1: Dimension, Snowflakes, and Average Distortion. | James R. Lee, Manor Mendel, Assaf Naor |
| 2004 | STOC | The two possible values of the chromatic number of a random graph. | Dimitris Achlioptas, Assaf Naor |
| 2004 | STOC | Approximating the cut-norm via Grothendieck's inequality. | Noga Alon, Assaf Naor |
| 2003 | FOCS | On the Maximum Satisfiability of Random Formulas. | Dimitris Achlioptas, Assaf Naor, Yuval Peres |
| 2003 | STOC | On metric ramsey-type phenomena. | Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor |
| 2002 | STOC | Girth and euclidean distortion. | Nathan Linial, Avner Magen, Assaf Naor |