Curriculum Vitae

Assaf Naor. Researcher Telephone Number: +1 425 705-8853 Theory Group, Microsoft Research Fax: +1 425 936-7329 One Microsoft Way Electronic Mail: anaor@microsoft.com Redmond, Washington 98052-6399 USA

Employment:

• 2002- 2004: Post-doctoral Researcher, Theory Group, Microsoft Research.

• 2004-present: Researcher, Theory Group, Microsoft Research.

• 2005-present: Affiliate Assistant Professor of Mathematics, University of Washington.

\underline{Education:}

1993-1996: Studies for a B.Sc. degree in Mathematics at the Hebrew University in Jerusalem. Graduated Summa Cum Laude in 1996.

1996-1998: Studies for an M.Sc. degree in Mathematics at the Hebrew University in Jerusalem. M.Sc. thesis: ”Geometric Problems in Non-Linear Functional Analysis”, prepared under the supervision of Professor Joram Lindenstrauss. Graduated Summa Cum Laude in 1998.

1998-2002: Studies for a Ph.D. degree at the Hebrew University in Jerusalem, under the supervision of Professor Joram Lindenstrauss. Thesis title: ”Linear and Non-Linear Geometric Problems in Banach Spaces”.

Research Interests:

• Analysis. • Probability. • Convex geometry.

• Linear and non-linear geometric Banach space theory.

• Structure theory of discrete metric spaces.

• Applications of the above to theoretical computer science, combinatorics and mathematical physics.

Professional Activities:

• Editor of the journal “Theory of Computing”. Journal web-site:

  http://theoryofcomputing.org/.

• Member of the program committee of STOC 2006. Conference web site:

  http://www.cs.washington.edu/stoc06/.

• Member of the American Mathematical Society.

• Member of the Association of Computing Machinery Special Interest Group on Algorithms and Computation Theory.

• Referee of research articles in the journals: Israel Journal of Mathematics, Geometric and Functional Analysis, Proceedings of the American Mathematical Society, Journal of Functional Analysis, Mathematiche Annalen, Random Structures and Algorithms, Annals of Probability, Journal of the Association of Computing Machinery, Advances in Mathematics, Arkiv der Mathematik, Journal of the American Mathematical Society, Combinatorica, ACM Transactions on Algorithms, International Mathematics Research Notices, SIAM Journal on Computing.

• Referee of research articles in the conferences: STOC, FOCS, RANDOM, SODA, CCC, SOCG.

• Reviewer of grant proposals for the Israeli Science Foundation, NSA.

Awards and Scholarships:

• Hebrew University rector’s prize for the academic years 1994-1995, 1996-1997, and the Dean of the Natural Sciences Faculty award for excellence in the M.Sc. studies, 1998.

• The Intel prize for B.Sc. students for the academic year 1995-1996.

• Award for excellence in the academic studies from the Israeli parliament (the Kneset), 1998.

• The Klein prize for excellence in teaching, 1998.

• The Clore Scholarship for Ph.D. students, 2000.

• European Union Marie Curie fellowship at University College, London, March-June 2001.

Teaching Experience:

Worked as a teaching assistant in the Hebrew University in Jerusalem in the academic years 1996-1997, 1997-1998, 1998-1999, 1999-2000, 2001-2002. This work involved teaching frontal recitation classes, and grading homework and exams. The courses taught were:

• First year linear algebra (linear algebra 1 and linear algebra 2).

• Differential and integral calculus for economics students.

• Complex function theory (for third year students).

• Probability 2 (advanced probability theory for second/third year students).

• Basic concepts in analysis (an advanced analysis course for M.Sc. students. This is a two-semester course that was taught for two years in a row).

• First year infinitesimal calculus (infinitesimal calculus 1 and infinitesimal calculus 2).

• Advanced calculus 1 (for second year students).

Advising: Mentor of James R. Lee as an intern in Microsoft Research, May–September 2003. Mentor of Lior Silberman and James R. Lee as interns in Microsoft Research June–September 2004. Mentor of Nir Avni, Konstantin Makarychev and Yury Makarychev as interns in Microsoft Research June–September 2005.

Invited tutorial: Workshop on Linear Analysis and probability, Texas A&M University, July 2003. The tutorial on metric space theory was directed toward graduate students in Mathematics and Theoretical Computer Science.

Invited tutorial: IPAM workshop on Multiscale Geometry and Analysis in High Dimensions, UCLA, September 2004.

Publications and preprints:

Published/accepted for publication:

• On the Turán Number of the Hexagon (with Z. Füredi and J. Verstraete), to appear in Advances in Mathematics. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/hexagons.pdf

• Some applications of Ball’s extension theorem (with M. Mendel), to appear in the Proceedings of the American Mathematical Society.

• Quadratic forms on graphs (with N. Alon, K. Makarychev and Y. Makarychev), to appear in Inventiones Mathematicae. A conference version appeared in STOC 2005.

• Euclidean distortion and the Sparsest Cut (with S. Arora and J. R. Lee). A conference version appeared in STOC 2005.

• Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs (with Y. Rabani and A. Sinclair), to appear in Journal of Functional Analysis.

• Rigorous location of phase transitions in hard optimization problems (with D. Achlioptas and Y. Peres), Nature 435, 759-764 (2005).

• Measured descent: A new embedding method for finite metrics (with R. Krauthgamer, J. R. Lee and M. Mendel), to appear in Geometric and Functional Analysis (GAFA). A conference version appeared in FOCS 2004. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/descent.pdf • Extending Lipschitz functions via random metric partitions (with J. R. Lee),

Inventiones Mathematicae 160 (2005), no. 1, 59-95. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/EXTdiff.pdf

• On Metric Ramsey-type Dichotomies (with Y. Bartal, N. Linial and M. Mendel), Journal of the London Mathematical Society 71, no. 2, 289-303 (2005). Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/Dichotomy.pdf

• A Note on Bipartite Graphs without a 2k-Cycle (with J. Verstraete). To appear in Combinatorics, Probability, and Computing. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/bipartitec2k.pdf

• Limitations to Frechet’s Metric Embedding Method (with Y. Bartal, N. Linial and M. Mendel), to appear in the Israel Journal of Mathematics. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/FRECHET.pdf

• Metric structures in L_{1}: Dimension, snowflakes, and average distortion (with J. R. Lee and M. Mendel). To appear in the European Journal of Combinatorics. A conference version of this paper appeared in LATIN 2004 (Buenos Aires). Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/L1structurejournal.pdf

• Solution of Shannon’s Problem on the Monotonicity of Entropy (with K. Ball, F. Barthe and S. Artstein), Journal of the American Mathematical Society 17, 975-982 (2004). Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/growth.pdf

• The Two Possible Values of the Chromatic Number of a Random Graph (with D. Achlioptas). To appear in the Annals of Mathematics. A conference version appeared in STOC 2004. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/chromatic.pdf

• Approximating the Cut-Norm via Grothendieck’s Inequality (with N. Alon). To appear in the SIAM Journal on Computing (STOC 2004 special issue). Conference version appeared in STOC 2004. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/cutnorm.pdf

• On Metric Ramsey Type Phenomena (with Y. Bartal, N. Linial and M. Mendel), to appear in the Annals of Mathematics. A conference version of this paper has appeared in STOC 2003. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/Ramsey.pdf

• Embedding the Diamond Graph in L_{p} and Dimension Reduction in L_{1} (with J. R. Lee), Geometric and Functional Analysis (GAFA) 14(4), 745-747 (2004). Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/diamond1.pdf

• Euclidean Quotients of Finite Metric Spaces (with M. Mendel), Advances in Mathematics 189(2), 451-494 (2004). Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/qpaperfin.pdf • A Probabilistic Approach to the Geometry of the ℓ_{p}^{n} Ball (with F. Barthe, O.

Guedon and S. Mendelson), Annals of Probability 33 (2005), no. 2, 480-513. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/LPBALL.pdf

• Entropy Jumps in the Presence of a Spectral Gap (with K. Ball and F. Barthe), Duke Mathematical Journal 119, No. 1, 41-63 (2003). Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/entropyduke.pdf

• On the Rate of Convergence in the Entropic Central Limit Theorem (with K. Ball, F. Barthe and S. Artstein), Probability Theory and Related Fields 129, 381-390 (2004). Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/entclt.pdf

• Absolute Lipschitz extendability (with J. R. Lee), to appear in Comptes Rendus de l’Acadmie des Sciences - Series I - Mathematics 338(11): 859-862, 2004. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/ext-cras.pdf

• The Fraction of Satisfiable Clauses in a Typical Formula (with D. Achlioptas and Y. Peres). Conference version appeared in FOCS 2003, pages 362–370. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/max.pdf

• Low Dimensional Embeddings of Ultrametrics (with Y. Bartal, N. Linial and M. Mendel), European Journal of Combinatorics, 25 (2004), no. 1, 87-92. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/Lowdim.pdf

• Projecting the Surface Measure of the Sphere of ℓ_{p}^{n} (with D. Romik), Annales de l’Institut Henri Poincaré (B), Probability and Statistics 39 (2003), 241-261. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/totvar2002.pdf

• Lipschitz Sums of Convex Functions (with M. Csörnyei), Studia Mathematica 158 (2003), 269-286. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/lipconv.pdf

• On Some Low Distortion Metric Ramsey Problems (with Y. Bartal, N. Linial and M. Mendel), Discrete and Computational Geometry 33(1), 27-45 (2005). Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/lowdistfin.pdf

• Girth and Euclidean Distortion (with N. Linial and A. Magen), Geometric and Functional Analysis (GAFA)12 (2002), no. 2, 380-394. A conference version of this paper has appeared in STOC 2002. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/girth.pdf

• Remarks on Non Linear type and Pisier’s Inequality (with G. Schechtman), Journal fur die reine und angewandte mathematik (Crelle’s Journal) 552 (2002) 213-236. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/umdfin.pdf

• Hyperplane Projections of the Unit Ball of ℓ_{p}^{n} (with F. Barthe), Discrete and Computational Geometry 27 (2002), no. 2, 215- 226. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/shadow.pdf • Boolean Functions whose Fourier Transform is Concentrated on the First Two

Levels (with E. Friedgut and G. Kalai), Advances in Applied Mathematics 29, no. 3, (2002) 427-437. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/social.pdf

• A Note on Simultaneous Polar and Cartesian Decomposition (with F. Barthe and M. Csörnyei), Geometric Aspects of Functional Analysis, Springer Lecture Notes in Mathematics 1807, 1-19. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/product.pdf

• The Surface Measure and Cone Measure on the Sphere of ℓ_{p}^{n}, to appear in the Transactions of the AMS. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/elpcone.pdf

• A Phase Transition Phenomenon Between the Isometric and Isomorphic Extension Problems for Holder Functions Between L_{p} Spaces, Mathematika 48 (2001), 253-271. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/extension.pdf

• Isomorphic Embedding of ℓ_{p}^{n} , 1 < p < 2, into ℓ_{1}^{(1+ϵ)n}(with A. Zvavitch), Israel Journal of Mathematics 122 (2001), 371-380. Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/isomorph.pdf

Submitted:

• Metric decomposition, smooth measures, and clustering (with J. R. Lee). Available at: http://research.microsoft.com/research/theory/naor/homepage%20files/cluster.pdf

• Parity check matrices and product representations of squares (with J. Verstraete).

• Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces (with Y. Peres, O. Schramm and S. Sheffield).

• Nearest neighbor preserving embeddings (with P. Indyk).

• Nonembeddabilty theorems via Fourier analysis (with S. Khot).

• Scaled Enflo type is equivalent to Rademacher type (with M. Mendel).

Invited Talks and Visiting Positions:

• Invited talk, International Workshop on Geometric Convex Analysis, Technion, Israel. March 2000.

• Invited talk, International Functional Analysis Meeting, Valencia, Spain. July 2000.

• Invited talk, Functional analysis session of the Israeli Mathematical Union meeting, Weizmann Institute, Israel. June 2001.

• Three invited talks, Workshop on Linear Analysis and Probability and SUMMIRFAS conference, College Station, Texas.July-August 2001.

• Invited Talk, Conference on Convex Geometric Analysis, Crete, Greece. August 2001.

• Invited talk, GAFA seminar, Tel-Aviv, Israel. November 2001.

• Invited talk, analysis seminar, Technion, Israel. December 2001.

• Invited talk, analysis seminar, University of Paris 6, Paris France. January 2002.

• Invited talk, analysis seminar, University of Marne-la-Valee, France. January 2002.

• Visiting researcher, Australian National University, Canberra, Australia. February 2002.

• Invited talk, Workshop on Discrete Metric Spaces and their Algorithmic Applications, Haifa University, March 2002.

• Invited talk, Conference on Geometric and Topological Aspects of Functional Analysis, Haifa University, May, 2002.

• Invited talk, analysis seminar, University of Marne-la-Valee, France. May 2002.

• Two invited talks, thematic program on asymptotic geometric analysis, Pacific Institute of Mathematics, Vancouver BC, Canada. July-August 2002.

• Invited talk, Combinatorics/Geometry seminar, University of Washington, Seattle WA, USA. October 2002.

• Short term visitor (November 1-15 2002), Institute for Advanced Study, Princeton NJ, USA. Invited talk at the Theoretical Computer Science and Discrete Mathematics seminar.

• Invited talk, Probability Seminar, University of Washington, Seattle WA, USA. November 2002.

• Invited talk, national meeting of the American Mathematical Society, special session on Banach spaces and convex geometry, Baltimore MD, USA, January 2003.

• Visiting fellow, Research School of Information Sciences and Engineering, The Australian National University, Canberra, Australia, February 2003.

• Mathematics colloquium talk, The Australian National University, Canberra, Australia, February 2003.

• Invited talk, Conference on Banach Spaces and Convex Geometric Analysis, Kiel, Germany, April 2003.

• Invited tutorial, Workshop on linear analysis and probability, College Station Texas, July 2003.

• Two invited talks, Workshop on discrete metric spaces and their algorithmic application, Princeton, August 2003.

• Invited talk, session on analysis on singular spaces, sectional AMS meeting, Boulder CO, October 2003.

• Invited talk, probability seminar, U. C. Berkeley, October 2003.

• Invited talk, complex analysis seminar, University of Washington, October 2003.

• Invited talk, theory of computing seminar, MIT, October 2003.

• Invited talk, theory of computing seminar, University of Washington, November 2003.

• Visiting fellow, Research School of Information Sciences and Engineering, The Australian National University, Canberra, Australia, November 2003.

• Invited talk, Geometry seminar, New York University, March 2004.

• Invited talk at the Pacific Northwest Theory of Computing Day, Microsoft, May 2004.

• Invited talk, Columbia Applied Probability Day, Columbia University, May 2004.

• Invited talk, GAFA seminar, Tel-Aviv University, May 2004.

• Invited talk, Workshop on Mathematical Foundations of Computer Science, ETH Zürich, May 2004.

• Invited talk, Workshop on Recent Developments in Finite Metric Spaces: Theory and Algorithmic Applications, Haifa University, June 2004.

• Invited talk, conference on Mathematical Foundations of Learning Theory, Barcelona, June 2004.

• Invited talk, Banff workshop on Convex Geometric Analysis, July 2004.

• Invited tutorial, IPAM workshop on Multiscale Geometry and Analysis in High Dimensions, UCLA, September 2004.

• Invited talk, mathematics colloquium, Georgia Institute of Technology, October 2004.

• Invited talk, combinatorics and optimization seminar, University of Waterloo, October 2004.

• Invited talk, IPAM workshop Multiscale structures in the analysis of High-DimensionalData, UCLA, October 2004.

• Invited talk, analysis seminar, Caltech, October 2004.

• Invited talk, probability seminar, U. C. Berkeley, November 2004.

• Invited talk, theory of computing seminar, University of Washington, November 2004.

• Invited talk, Applied and Computational Mathematics Colloquium, CALTECH, November 2004.

• Invited talk, IPAM workshop on Math Analysis and Multiscale Geometric Analysis., UCLA, November 2004.

• Invited talk, theory of computing seminar, U. C. Berkeley, December 2004.

• Invited talk, mathematics colloquium, U. C. Berkeley, December 2004.

• Invited talk, Conference on Harmonic Analysis, Ergodic Theory and Probability (a conference in honor of I. Katznelson’s 70th Birthday), Stanford, December 2004.

• Invited talk, probability seminar, University of Washington, February 2005.

• Invited talk, algorithms seminar, Stanford University, February 2005.

• Invited talk, mathematics colloquium, Courant Institute, New York University, March 2005.

• Invited talk, analysis seminar, Weizmann Institute, March 2005.

• Invited talk, mathematics colloquium, Hebrew University, Jerusalem, March 2005.

• Invited talk, GAFA seminar, Tel-Aviv University, April 2005.

• Invited talk, analysis seminar, Stanford University, April 2005.

• Invited talk, applied mathematics colloquium, MIT, April 2005.

• Invited talk, analysis seminar, MIT, April 2005.

• Invited talk, applied mathematics colloquium, Harvard University, April 2005.

• Invited talk, analysis seminar, UCLA, May 2005.

• Invited talk, Contemporary Ramifications of Banach Space Theory (conference in honor of Joram Lindenstrauss and Lior Tzafriri), Hebrew University, Jerusalem, June 2005.

• Invited talk, Asymptotic Geometric Analysis (conference in honor of Nicole Tomczak-Jaegermann), Dead Sea, June 2005.

• Invited talk, conference in honor of Haskell Rosenthal, Texas A&M University, August 2005.

• Invited talk, mathematics colloquium, University of Minnesota, September 2005.

• Invited talk, Industrial Problems Seminar, University of Minnesota, September 2005.

• Plenary address, Southeast Section Meeting of the American Mathematical Society, October 2005.

• Invited talk, Computer science/discrete mathematics seminar, Institute for Advanced Study, October 2005.

• Invited talk, mathematics colloquium, Princeton University, October 2005.