default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDAssaf Naor
Person information
- affiliation: Princeton University, Mathematics Department, NJ, USA
- affiliation (former): Microsoft Research
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2021
[c40]Vijay Bhattiprolu, Euiwoong Lee
, Assaf Naor:
A framework for quadratic form maximization over convex sets through nonconvex relaxations. STOC 2021: 870-881- 2020
- [j22]Assaf Naor, Gilles Pisier, Gideon Schechtman:
Impossibility of Dimension Reduction in the Nuclear Norm. Discret. Comput. Geom. 63(2): 319-345 (2020)
2010 – 2019
- 2019
- [c39]Subhash Khot, Assaf Naor:
The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics. SODA 2019: 1814-1824 - [i25]Ronen Eldan, Assaf Naor:
Krivine diffusions attain the Goemans-Williamson approximation ratio. CoRR abs/1906.10615 (2019) - 2018
- [c38]Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten:
Hölder Homeomorphisms and Approximate Nearest Neighbors. FOCS 2018: 159-169 - [c37]Assaf Naor, Gilles Pisier, Gideon Schechtman:
Impossibility of dimension reduction in the nuclear norm. SODA 2018: 1345-1352 - [c36]Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten:
Data-dependent hashing via nonlinear spectral gaps. STOC 2018: 787-800 - [i24]Assaf Naor:
Metric dimension reduction: A snapshot of the Ribe program. CoRR abs/1809.02376 (2018) - [i23]Subhash Khot, Assaf Naor:
The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics. CoRR abs/1810.04321 (2018) - 2017
- [c35]Assaf Naor:
A Spectral Gap Precludes Low-Dimensional Embeddings. SoCG 2017: 50:1-50:16 - [c34]Assaf Naor:
Probabilistic clustering of high dimensional norms. SODA 2017: 690-709 - [c33]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: 564-575 - [i22]Assaf Naor, Robert Young:
Vertical perimeter versus horizontal perimeter. CoRR abs/1701.00620 (2017) - [i21]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 abs/1704.01200 (2017) - [i20]Assaf Naor, Gilles Pisier, Gideon Schechtman:
Impossibility of dimension reduction in the nuclear norm. CoRR abs/1710.08896 (2017) - 2016
- [c32]Alexandr Andoni, Assaf Naor, Ofer Neiman:
Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. ICALP 2016: 83:1-83:14 - [i19]Assaf Naor:
A spectral gap precludes low-dimensional embeddings. CoRR abs/1611.08861 (2016) - 2014
- [j21]Assaf Naor, Oded Regev, Thomas Vidick:
Efficient Rounding for the Noncommutative Grothendieck Inequality. Theory Comput. 10: 257-295 (2014) - [c31]Manor Mendel, Assaf Naor:
Expanders with respect to Hadamard spaces and random graphs: extended abstract. ITCS 2014: 353-358 - 2013
- [j20]Assaf Naor:
Every graph is essentially sparse. Commun. ACM 56(8): 86 (2013) - [j19]Steven Heilman, Aukosh Jagannath, Assaf Naor:
Solution of the Propeller Conjecture in ℝ3. Discret. Comput. Geom. 50(2): 263-305 (2013) - [j18]Subhash Khot, Assaf Naor:
Sharp kernel clustering algorithms and their associated Grothendieck inequalities. Random Struct. Algorithms 42(3): 269-300 (2013) - [c30]Assaf Naor, Oded Regev, Thomas Vidick:
Efficient rounding for the noncommutative grothendieck inequality. STOC 2013: 71-80 - [i18]Manor Mendel, Assaf Naor:
Expanders with respect to Hadamard spaces and random graphs. CoRR abs/1306.5434 (2013) - 2012
- [j17]Assaf Naor:
On the Banach-Space-Valued Azuma Inequality and Small-Set Isoperimetry of Alon-Roichman Graphs. Comb. Probab. Comput. 21(4): 623-634 (2012) - [c29]Steven Heilman, Aukosh Jagannath, Assaf Naor:
Solution of the propeller conjecture in R3. STOC 2012: 269-276 - [i17]Jop Briët, Assaf Naor, Oded Regev:
Locally decodable codes and the failure of cotype for projective tensor products. CoRR abs/1208.0539 (2012) - [i16]Assaf Naor, Oded Regev, Thomas Vidick:
Efficient rounding for the noncommutative Grothendieck inequality. CoRR abs/1210.7656 (2012) - 2011
- [c28]Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor:
The Grothendieck Constant is Strictly Smaller than Krivine's Bound. FOCS 2011: 453-462 - [c27]Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, János Pach:
Overlap properties of geometric expanders. SODA 2011: 1188-1197 - [i15]Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor:
The Grothendieck constant is strictly smaller than Krivine's bound. CoRR abs/1103.6161 (2011) - [i14]Subhash Khot, Assaf Naor:
Grothendieck-type inequalities in combinatorial optimization. CoRR abs/1108.2464 (2011) - [i13]Steven Heilman, Aukosh Jagannath, Assaf Naor:
Solution of the propeller conjecture in $\R^3$. CoRR abs/1112.2993 (2011) - 2010
- [j16]Manor Mendel, Assaf Naor:
Maximum gradient embeddings and monotone clustering. Comb. 30(5): 581-615 (2010) - [j15]William B. Johnson, Assaf Naor:
The Johnson-Lindenstrauss Lemma Almost Characterizes Hilbert Space, But Not Quite. Discret. Comput. Geom. 43(3): 542-553 (2010) - [j14]Tim Austin, Assaf Naor, Alain Valette:
The Euclidean Distortion of the Lamplighter Group. Discret. Comput. Geom. 44(1): 55-74 (2010) - [j13]Guy Kindler, Assaf Naor, Gideon Schechtman:
The UGC Hardness Threshold of the Lp Grothendieck Problem. Math. Oper. Res. 35(2): 267-283 (2010) - [c26]Manor Mendel, Assaf Naor:
Towards a Calculus for Non-Linear Spectral Gaps. SODA 2010: 236-255 - [c25]Subhash Khot, Assaf Naor:
Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities. SODA 2010: 664-683 - [i12]Assaf Naor:
L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry. CoRR abs/1003.4261 (2010) - [i11]Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, János Pach:
Overlap properties of geometric expanders. CoRR abs/1005.1392 (2010)
2000 – 2009
- 2009
- [c24]Jeff Cheeger, Bruce Kleiner, Assaf Naor:
A (log n)Omega(1) Integrality Gap for the Sparsest Cut SDP. FOCS 2009: 555-564 - [c23]William B. Johnson, Assaf Naor:
The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite. SODA 2009: 885-891 - [i10]Subhash Khot, Assaf Naor:
Sharp kernel clustering algorithms and their associated Grothendieck inequalities. CoRR abs/0906.4816 (2009) - [i9]Jeff Cheeger, Bruce Kleiner, Assaf Naor:
A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP. CoRR abs/0910.2024 (2009) - [i8]Jeff Cheeger, Bruce Kleiner, Assaf Naor:
Compression bounds for Lipschitz maps from the Heisenberg group to L1. CoRR abs/0910.2026 (2009) - 2008
- [j12]Assaf Naor, Jacques Verstraëte:
Parity check matrices and product representations of squares. Comb. 28(2): 163-185 (2008) - [j11]Subhash Khot, Assaf Naor:
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. SIAM J. Comput. 38(4): 1448-1463 (2008) - [c22]Manor Mendel, Assaf Naor:
Markov convexity and local rigidity of distorted metrics. SCG 2008: 49-58 - [c21]Subhash Khot, Assaf Naor:
Approximate Kernel Clustering. FOCS 2008: 561-570 - [c20]Guy Kindler, Assaf Naor, Gideon Schechtman:
The UGC hardness threshold of the ℓp Grothendieck problem. SODA 2008: 64-73 - [i7]William B. Johnson, Assaf Naor:
The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite. CoRR abs/0807.1919 (2008) - [i6]Subhash Khot, Assaf Naor:
Approximate kernel clustering. CoRR abs/0807.4626 (2008) - 2007
- [j10]Sanjeev Arora, James R. Lee, Assaf Naor:
Fréchet Embeddings of Negative Type Metrics. Discret. Comput. Geom. 38(4): 726-739 (2007) - [j9]Dimitris Achlioptas, Assaf Naor, Yuval Peres:
On the maximum satisfiability of random formulas. J. ACM 54(2): 10 (2007) - [j8]Assaf Naor, Gideon Schechtman:
Planar Earthmover Is Not in L1. SIAM J. Comput. 37(3): 804-826 (2007) - [j7]Rajeev Motwani, Assaf Naor, Rina Panigrahy:
Lower Bounds on Locality Sensitive Hashing. SIAM J. Discret. Math. 21(4): 930-935 (2007) - [j6]Piotr Indyk, Assaf Naor:
Nearest-neighbor-preserving embeddings. ACM Trans. Algorithms 3(3): 31 (2007) - [c19]Manor Mendel, Assaf Naor:
Maximum Gradient Embeddings and Monotone Clustering. APPROX-RANDOM 2007: 242-256 - [c18]Subhash Khot, Assaf Naor:
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. FOCS 2007: 318-328 - 2006
- [j5]Noga Alon, Assaf Naor:
Approximating the Cut-Norm via Grothendieck's Inequality. SIAM J. Comput. 35(4): 787-803 (2006) - [c17]Rajeev Motwani, Assaf Naor, Rina Panigrahy:
Lower bounds on locality sensitive hashing. SCG 2006: 154-157 - [c16]James R. Lee, Assaf Naor:
Lp metrics on the Heisenberg group and the Goemans-Linial conjecture. FOCS 2006: 99-108 - [c15]Manor Mendel, Assaf Naor:
Ramsey partitions and proximity data structures. FOCS 2006: 109-118 - [c14]Assaf Naor, Gideon Schechtman:
Planar Earthmover is not in L_1. FOCS 2006: 655-666 - [c13]Manor Mendel, Assaf Naor:
Metric cotype. SODA 2006: 79-88 - [c12]James R. Lee, Assaf Naor, Yuval Peres:
Trees and Markov convexity. SODA 2006: 1028-1037 - [i5]Manor Mendel, Assaf Naor:
Maximum gradient embeddings and monotone clustering. CoRR abs/cs/0606109 (2006) - 2005
- [j4]Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor:
Some Low Distortion Metric Ramsey Problems. Discret. Comput. Geom. 33(1): 27-41 (2005) - [j3]James R. Lee, Manor Mendel, Assaf Naor:
Metric structures in L1: dimension, snowflakes, and average distortion. Eur. J. Comb. 26(8): 1180-1190 (2005) - [c11]Subhash Khot, Assaf Naor:
Nonembeddability theorems via Fourier analysis. FOCS 2005: 101-112 - [c10]Assaf Naor, Jacques Verstraëte:
Improved bounds on the size of sparse parity check matrices. ISIT 2005: 1749-1752 - [c9]Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor:
Quadratic forms on graphs. STOC 2005: 486-493 - [c8]Sanjeev Arora, James R. Lee, Assaf Naor:
Euclidean distortion and the sparsest cut. STOC 2005: 553-562 - [i4]Assaf Naor, Gideon Schechtman:
Planar Earthmover is not in L1. CoRR abs/cs/0509074 (2005) - [i3]Rajeev Motwani, Assaf Naor, Rina Panigrahy:
Lower bounds on Locality Sensitive Hashing. CoRR abs/cs/0510088 (2005) - [i2]Manor Mendel, Assaf Naor:
Ramsey partitions and proximity data structures. CoRR abs/cs/0511084 (2005) - 2004
- [j2]Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor:
Low dimensional embeddings of ultrametrics. Eur. J. Comb. 25(1): 87-92 (2004) - [c7]Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor:
Measured Descent: A New Embedding Method for Finite Metrics. FOCS 2004: 434-443 - [c6]James R. Lee, Manor Mendel, Assaf Naor:
Metric Structures in L1: Dimension, Snowflakes, and Average Distortion. LATIN 2004: 401-412 - [c5]Noga Alon, Assaf Naor:
Approximating the cut-norm via Grothendieck's inequality. STOC 2004: 72-80 - [c4]Dimitris Achlioptas, Assaf Naor:
The two possible values of the chromatic number of a random graph. STOC 2004: 587-593 - [i1]Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor:
Measured descent: A new embedding method for finite metrics. CoRR abs/cs/0412008 (2004) - 2003
- [c3]Dimitris Achlioptas, Assaf Naor, Yuval Peres:
On the Maximum Satisfiability of Random Formulas. FOCS 2003: 362-370 - [c2]Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor:
On metric ramsey-type phenomena. STOC 2003: 463-472 - 2002
- [j1]Ehud Friedgut, Gil Kalai, Assaf Naor:
Boolean functions whose Fourier transform is concentrated on the first two levels. Adv. Appl. Math. 29(3): 427-437 (2002) - [c1]Nathan Linial, Avner Magen, Assaf Naor:
Girth and euclidean distortion. STOC 2002: 705-711
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:14 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
