Assaf Naor

Calculated based on number of publications stored in Pure and citations from Scopus
20012023

Research activity per year

Filter
Conference contribution

Search results

  • 2021

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

    Bhattiprolu, V., Lee, E. & Naor, A., Jun 15 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, p. 870-881 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    3 Scopus citations
  • 2018

    Data-Dependent hashing via nonlinear spectral gaps

    Andoni, A., Naor, A., Nikolov, A., Razenshteyn, I. & Waingarten, E., Jun 20 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 685-698 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    18 Scopus citations
  • Hölder homeomorphisms and approximate nearest neighbors

    Andoni, A., Naor, A., Nikolov, A., Razenshteyn, I. & Waingarten, E., Nov 30 2018, Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. Thorup, M. (ed.). IEEE Computer Society, p. 159-169 11 p. 8555102. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2018-October).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    19 Scopus citations
  • Impossibility of dimension reduction in the nuclear norm

    Naor, A., Pisier, G. & Schechtman, G., 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). Association for Computing Machinery, p. 1345-1352 8 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    6 Scopus citations
  • Metric dimension reduction: A snapshot of the Ribe program

    Naor, A., 2018, Invited Lectures. Sirakov, B., de Souza, P. N. & Viana, M. (eds.). World Scientific Publishing Co. Pte Ltd, p. 759-838 80 p. (Proceedings of the International Congress of Mathematicians, ICM 2018; vol. 1).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    26 Scopus citations
  • 2017

    A spectral gap precludes low-dimensional embeddings

    Naor, A., Jun 1 2017, 33rd International Symposium on Computational Geometry, SoCG 2017. Katz, M. J. & Aronov, B. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 501-5016 4516 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 77).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    7 Scopus citations
  • Probabilistic clustering of high dimensional norms

    Naor, A., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 690-709 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    4 Scopus citations
  • The integrality gap of the goemans-linial SDP relaxation for sparsest cut is at least a constant multiple of √logn

    Naor, A. & Young, R., Jun 19 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). Association for Computing Machinery, p. 564-575 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    7 Scopus citations
  • 2016

    Impossibility of sketching of the 3D transportation metric with quadratic cost

    Andoni, A., Naor, A. & Neiman, O., Aug 1 2016, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. Rabani, Y., Chatzigiannakis, I., Sangiorgi, D. & Mitzenmacher, M. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 83. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 55).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    5 Scopus citations
  • 2014

    Expanders with respect to hadamard spaces and random graphs

    Mendel, M. & Naor, A., 2014, ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery, p. 353-358 6 p. (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    1 Scopus citations
  • 2013

    Efficient rounding for the noncommutative grothendieck inequality

    Naor, A., Regev, O. & Vidick, T., 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 71-80 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    18 Scopus citations
  • 2012

    Solution of the propeller conjecture in ℝ 3

    Heilman, S., Jagannath, A. & Naor, A., 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 269-276 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2011

    Overlap properties of geometric expanders

    Fox, J., Gromov, M., Lafforgue, V., Naor, A. & Pach, J., May 12 2011, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. p. 1188-1197 10 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    6 Scopus citations
  • The Grothendieck constant is strictly smaller than Krivine's bound

    Braverman, M., Makarychev, K., Makarychev, Y. & Naor, A., 2011, Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. p. 453-462 10 p. 6108206. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    27 Scopus citations
  • 2010

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

    Naor, A., 2010, Proceedings of the International Congress of Mathematicians 2010, ICM 2010. p. 1549-1575 27 p. (Proceedings of the International Congress of Mathematicians 2010, ICM 2010).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    33 Scopus citations
  • Sharp kernel clustering algorithms and their associated Grothendieck inequalities

    Khot, S. & Naor, A., 2010, Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. p. 664-683 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    6 Scopus citations
  • Towards a calculus for non-linear spectral gaps

    Mendel, M. & Naor, A., 2010, Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. p. 236-255 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    9 Scopus citations
  • 2009

    A (log n)Ω(1) integrality gap for the sparsest cut SDP

    Cheeger, J., Kleiner, B. & Naor, A., 2009, Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009. p. 555-564 10 p. 5438599. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    34 Scopus citations
  • The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite

    Johnson, W. B. & Naor, A., 2009, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery, p. 885-891 7 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    4 Scopus citations
  • 2008

    Approximate kernel clustering

    Khot, S. & Naor, A., 2008, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008. p. 561-570 10 p. 4690989. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    9 Scopus citations
  • Markov convexity and local rigidity of distorted metrics

    Mendel, M. & Naor, A., 2008, Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08. p. 49-58 10 p. (Proceedings of the Annual Symposium on Computational Geometry).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    10 Scopus citations
  • The UGC hardness threshold of the l p Grothendieck problem

    Kindler, G., Naor, A. & Schechtman, G., 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 64-73 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    5 Scopus citations
  • 2007

    Linear equations modulo 2 and the L1 diameter of convex bodies

    Khot, S. & Naor, A., 2007, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. p. 318-328 11 p. 4389503. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    6 Scopus citations
  • Maximum gradient embeddings and monotone clustering

    Mendel, M. & Naor, A., 2007, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings. Springer Verlag, p. 242-256 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4627 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    3 Scopus citations
  • 2006

    Lower bounds on locality sensitive hashing

    Motwani, R., Naor, A. & Panigrahy, R., 2006, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Association for Computing Machinery, p. 154-157 4 p. (Proceedings of the Annual Symposium on Computational Geometry; vol. 2006).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    43 Scopus citations
  • Lp metrics on the Heisenberg group and the Goemans-Linial conjecture

    Lee, J. R. & Naor, A., Dec 1 2006, 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006. p. 99-108 10 p. 4031347. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    57 Scopus citations
  • Planar earthmover is not in L1

    Naor, A. & Schechtman, G., Dec 1 2006, 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006. p. 655-664 10 p. 4031400. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    5 Scopus citations
  • Ramsey partitions and proximity data structures

    Mendel, M. & Naor, A., 2006, 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006. p. 109-118 10 p. 4031348. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    37 Scopus citations
  • 2005

    Improved bounds on the size of sparse parity check matrices

    Naor, A. & Verstraete, J., Dec 1 2005, Proceedings of the 2005 IEEE International Symposium on Information Theory, ISIT 05. p. 1749-1752 4 p. 1523645. (IEEE International Symposium on Information Theory - Proceedings; vol. 2005).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Nonembeddability theorems via Fourier analysis

    Khot, S. & Naor, A., 2005, Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. p. 101-110 10 p. 1530705. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2005).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    22 Scopus citations
  • 2003

    On the maximum satisfiability of random formulas

    Achlioptas, D., Naor, A. & Peres, Y., 2003, Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003. IEEE Computer Society, p. 362-370 9 p. 1238210. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2003-January).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    6 Scopus citations