Assaf Naor

  • Source: Scopus
  • Calculated based on no. of publications stored in Pure and citations from Scopus
20012021

Research activity per year

If you made any changes in Pure these will be visible here soon.
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

    Open Access
  • 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

    10 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

    11 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

    5 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

    16 Scopus citations
  • 2017

    A spectral gap precludes low-dimensional embeddings

    Naor, A., Jun 1 2017, 33rd International Symposium on Computational Geometry, SoCG 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 77. p. 501-5016 4516 p.

    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
    3 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

    6 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

    4 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

    16 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

    22 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

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

    Khot, S. & Naor, A., May 6 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., May 6 2010, Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. p. 236-255 20 p.

    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

    32 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

    8 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

    9 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

    2 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

    40 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

    53 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

    4 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

    33 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

    20 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