Geometry & Topology Volume 25, issue 4 (2021)

Download this article
	For screen
	For printing

Recent Issues

The Journal

Submission Guidelines

Submission Page

Policies for Authors

Ethics Statement

ISSN 1364-0380 (online)

ISSN 1465-3060 (print)

Author Index

To Appear

Other MSP Journals

An average John theorem

Assaf Naor

Geometry & Topology 25 (2021) 1631–1717

DOI: 10.2140/gt.2021.25.1631

Bibliography

1	I Abraham, Y Bartal, O Neiman, Advances in metric embedding theory, Adv. Math. 228 (2011) 3026 MR2844939
2	F Albiac, F Baudier, Embeddability of snowflaked metrics with applications to the nonlinear geometry of the spaces L_p and ℓ_p for 0 < p < ∞, J. Geom. Anal. 25 (2015) 1 MR3299267
3	N Alon, The diameter of SL_n(𝔽_q), preprint (2019)
4	N Alon, P Frankl, V Rödl, Geometrical realization of set systems and probabilistic communication complexity, from: "26th Annual Symposium on Foundations of Computer Science", IEEE (1985) 277
5	N Alon, Y Roichman, Random Cayley graphs and expanders, Random Structures Algorithms 5 (1994) 271 MR1262979
6	N Alon, J H Spencer, The probabilistic method, Wiley (1992) MR1140703
7	A Andoni, P Indyk, I Razenshteyn, Approximate nearest neighbor search in high dimensions, from: "Proceedings of the International Congress of Mathematicians, IV" (editors B Sirakov, P N de Souza, M Viana), World Sci. (2018) 3287 MR3966533
8	A Andoni, A Naor, O Neiman, Snowflake universality of Wasserstein spaces, Ann. Sci. École Norm. Sup. 51 (2018) 657 MR3831034
9	A Andoni, A Naor, A Nikolov, I Razenshteyn, E Waingarten, Complex interpolation, Hölder homeomorphisms, and algorithmic applications, in preparation
10	A Andoni, A Naor, A Nikolov, I Razenshteyn, E Waingarten, Spectral partitioning of metric spaces, in preparation
11	A Andoni, A Naor, A Nikolov, I Razenshteyn, E Waingarten, Data-dependent hashing via nonlinear spectral gaps, from: "Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing" (editors I Diakonikolas, D Kempe, M Henzinger), ACM (2018) 787 MR3826294
12	A Andoni, A Naor, A Nikolov, I Razenshteyn, E Waingarten, Hölder homeomorphisms and approximate nearest neighbors, from: "59th Annual IEEE Symposium on Foundations of Computer Science" (editor M Thorup), IEEE (2018) 159 MR3899586
13	A Andoni, H L Nguyen, A Nikolov, I Razenshteyn, E Waingarten, Approximate near neighbors for general symmetric norms, from: "Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing" (editors H Hatami, P McKenzie, V King), ACM (2017) 902 MR3678238
14	D Andrén, L Hellström, K Markström, On the complexity of matrix reduction over finite fields, Adv. Appl. Math. 39 (2007) 428 MR2356430
15	J Arias-de-Reyna, L Rodríguez-Piazza, Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces, Israel J. Math. 79 (1992) 103 MR1195255
16	N Aronszajn, Differentiability of Lipschitzian mappings between Banach spaces, Studia Math. 57 (1976) 147 MR425608
17	T Austin, A Naor, A Valette, The Euclidean distortion of the lamplighter group, Discrete Comput. Geom. 44 (2010) 55 MR2639818
18	U Bader, A Furman, T Gelander, N Monod, Property (T) and rigidity for actions on Banach spaces, Acta Math. 198 (2007) 57 MR2316269
19	K Ball, Markov chains, Riesz transforms and Lipschitz maps, Geom. Funct. Anal. 2 (1992) 137 MR1159828
20	K Ball, The Ribe programme, from: "Séminaire Bourbaki, 2011/2012", Astérisque 352, Soc. Math. France (2013) 147 MR3087345
21	K Ball, E A Carlen, E H Lieb, Sharp uniform convexity and smoothness inequalities for trace norms, Invent. Math. 115 (1994) 463 MR1262940
22	S Banach, Théorie des opérations linéaires, 1, Inst. Mat. Polish Acad. Sci. (1932)
23	Y Bartal, N Linial, M Mendel, A Naor, On metric Ramsey-type phenomena, Ann. of Math. 162 (2005) 643 MR2183280
24	S Bates, W B Johnson, J Lindenstrauss, D Preiss, G Schechtman, Affine approximation of Lipschitz functions and nonlinear quotients, Geom. Funct. Anal. 9 (1999) 1092 MR1736929
25	F P Baudier, Quantitative nonlinear embeddings into Lebesgue sequence spaces, J. Topol. Anal. 8 (2016) 117 MR3463248
26	Y Benyamini, J Lindenstrauss, Geometric nonlinear functional analysis, I, 48, Amer. Math. Soc. (2000) MR1727673
27	J Bergh, J Löfström, Interpolation spaces: an introduction, 223, Springer (1976) MR0482275
28	J Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985) 46 MR815600
29	J Bourgain, The metrical interpretation of superreflexivity in Banach spaces, Israel J. Math. 56 (1986) 222 MR880292
30	J Bourgain, V Milman, H Wolfson, On type of metric spaces, Trans. Amer. Math. Soc. 294 (1986) 295 MR819949
31	J Bretagnolle, D Dacunha-Castelle, J L Krivine, Fonctions de type positif sur les espaces L^p, C. R. Acad. Sci. Paris 261 (1965) 2153 MR185628
32	A Brudnyi, Y Brudnyi, Methods of geometric analysis in extension and trace problems, II, 103, Birkhäuser (2012) MR2868143
33	Y Brudnyi, P Shvartsman, Stability of the Lipschitz extension property under metric transforms, Geom. Funct. Anal. 12 (2002) 73 MR1904557
34	A P Calderón, Intermediate spaces and interpolation, the complex method, Studia Math. 24 (1964) 113 MR167830
35	F Chaatit, On uniform homeomorphisms of the unit spheres of certain Banach lattices, Pacific J. Math. 168 (1995) 11 MR1331992
36	J Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, from: "Problems in analysis" (editor R C Gunning), Princeton Univ. Press (1970) 195 MR0402831
37	Q Cheng, Sphere equivalence, property H, and Banach expanders, Studia Math. 233 (2016) 67 MR3503071
38	J P R Christensen, Measure theoretic zero sets in infinite dimensional spaces and applications to differentiability of Lipschitz mappings, Publ. Dép. Math. (Lyon) 10 (1973) 29 MR361770
39	F R K Chung, Laplacians of graphs and Cheeger’s inequalities, from: "Combinatorics : Paul Erdős is eighty, II" (editors D Miklós, V T Sós, T Szőnyi), Bolyai Soc. Math. Stud. 2, János Bolyai Math. Soc. (1996) 157 MR1395858
40	J A Clarkson, Uniformly convex spaces, Trans. Amer. Math. Soc. 40 (1936) 396 MR1501880
41	M Cwikel, Complex interpolation spaces, a discrete definition and reiteration, Indiana Univ. Math. J. 27 (1978) 1005 MR511254
42	M Cwikel, S Reisner, Interpolation of uniformly convex Banach spaces, Proc. Amer. Math. Soc. 84 (1982) 555 MR643748
43	M Daher, Homéomorphismes uniformes entre les sphères unité des espaces d’interpolation, Canad. Math. Bull. 38 (1995) 286 MR1347300
44	G David, S Semmes, Fractured fractals and broken dreams, 7, Oxford Univ. Press (1997) MR1616732
45	M M Day, Uniform convexity in factor and conjugate spaces, Ann. of Math. 45 (1944) 375 MR10779
46	P Enflo, On the nonexistence of uniform homeomorphisms between L_p–spaces, Ark. Mat. 8 (1969) 103 MR271719
47	P Enflo, Banach spaces which can be given an equivalent uniformly convex norm, Israel J. Math. 13 (1972) 281 MR336297
48	P Enflo, Uniform homeomorphisms between Banach spaces, from: "Séminaire Maurey–Schwartz, 1975/1976 : Espaces, L^p, applications radonifiantes et géométrie des espaces de Banach", Cent. Math. École Polytech. (1976) MR0477709
49	A Eskenazis, A Naor, On coarse and uniform embeddings into L_p, in preparation
50	T Figiel, On the moduli of convexity and smoothness, Studia Math. 56 (1976) 121 MR425581
51	T Figiel, G Pisier, Séries aléatoires dans les espaces uniformément convexes ou uniformément lisses, C. R. Acad. Sci. Paris Sér. A 279 (1974) 611 MR358295
52	M Fréchet, Sur quelques points du calcul fonctionnel, Rend. Circ. Mat. Palermo 22 (1906) 1
53	I Gelfand, Abstrakte Funktionen und lineare Operatoren, Mat. Sb. 4 (1938) 235
54	R I Grigorchuk, P W Nowak, Diameters, distortion, and eigenvalues, European J. Combin. 33 (2012) 1574 MR2923470
55	M Gromov, Spaces and questions, from: "Visions in Mathematics: GAFA 2000, I" (editors N Alon, J Bourgain, A Connes, M Gromov, V Milman) (2000) 118 MR1826251
56	M Gromov, Random walk in random groups, Geom. Funct. Anal. 13 (2003) 73 MR1978492
57	J L Gross, Every connected regular graph of even degree is a Schreier coset graph, J. Combinatorial Theory Ser. B 22 (1977) 227 MR450121
58	O Hanner, On the uniform convexity of L^p and l^p, Ark. Mat. 3 (1956) 239 MR77087
59	A Hatcher, Algebraic topology, Cambridge Univ. Press (2002) MR1867354
60	J Heinonen, Lectures on analysis on metric spaces, Springer (2001) MR1800917
61	S Heinrich, Ultraproducts in Banach space theory, J. Reine Angew. Math. 313 (1980) 72 MR552464
62	M Herman, J Pakianathan, On the distribution of distances in homogeneous compact metric spaces, Topology Appl. 193 (2015) 97 MR3385083
63	S Hoory, N Linial, A Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006) 439 MR2247919
64	H Izeki, S Nayatani, Combinatorial harmonic maps and discrete-group actions on Hadamard spaces, Geom. Dedicata 114 (2005) 147 MR2174098
65	R C James, Super-reflexive Banach spaces, Canad. J. Math. 24 (1972) 896 MR320713
66	F John, Extremum problems with inequalities as subsidiary conditions, from: "Studies and essays presented to R Courant on his 60th birthday" (editor K O Friedrichs), Interscience (1948) 187 MR0030135
67	W B Johnson, J Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, from: "Conference in modern analysis and probability" (editors R Beals, A Beck, A Bellow, A Hajian), Contemp. Math. 26, Amer. Math. Soc. (1984) 189 MR737400
68	W B Johnson, J Lindenstrauss, Basic concepts in the geometry of Banach spaces, from: "Handbook of the geometry of Banach spaces, I" (editors W B Johnson, J Lindenstrauss), North-Holland (2001) 1 MR1863689
69	W B Johnson, J Lindenstrauss, G Schechtman, On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces, from: "Geometrical aspects of functional analysis" (editors J Lindenstrauss, V D Milman), Lecture Notes in Math. 1267, Springer (1987) 177 MR907694
70	P N Jolissaint, A Valette, L^p–distortion and p–spectral gap of finite graphs, Bull. Lond. Math. Soc. 46 (2014) 329 MR3194751
71	N J Kalton, The nonlinear geometry of Banach spaces, Rev. Mat. Complut. 21 (2008) 7 MR2408035
72	M Kassabov, Kazhdan constants for SL_n(ℤ), Int. J. Algebra Comput. 15 (2005) 971 MR2197816
73	S Khot, A Naor, Nonembeddability theorems via Fourier analysis, Math. Ann. 334 (2006) 821 MR2209259
74	M D Kirszbraun, Über die zusammenziehenden und Lipschitzchen Transformationen, Fund. Math. 22 (1934) 77
75	T Kondo, CAT(0) spaces and expanders, Math. Z. 271 (2012) 343 MR2917147
76	T J Laakso, Plane with A_∞–weighted metric not bi-Lipschitz embeddable to ℝ^N, Bull. Lond. Math. Soc. 34 (2002) 667 MR1924353
77	T de Laat, M de la Salle, Banach space actions and L²–spectral gap, Anal. PDE 14 (2021) 45
78	V Lafforgue, Un renforcement de la propriété (T), Duke Math. J. 143 (2008) 559 MR2423763
79	V Lafforgue, Propriété (T) renforcée banachique et transformation de Fourier rapide, J. Topol. Anal. 1 (2009) 191 MR2574023
80	J R Lee, A Naor, Extending Lipschitz functions via random metric partitions, Invent. Math. 160 (2005) 59 MR2129708
81	J Lindenstrauss, On the modulus of smoothness and divergent series in Banach spaces, Michigan Math. J. 10 (1963) 241 MR169061
82	J Lindenstrauss, L Tzafriri, Classical Banach spaces, I : Sequence spaces, 92, Springer (1977) MR0500056
83	J Lindenstrauss, L Tzafriri, Classical Banach spaces, II : Function spaces, 97, Springer (1979) MR540367
84	N Linial, E London, Y Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995) 215 MR1337355
85	N Linial, A Magen, Least-distortion Euclidean embeddings of graphs : products of cycles and expanders, J. Combin. Theory Ser. B 79 (2000) 157 MR1769197
86	N Linial, A Magen, A Naor, Girth and Euclidean distortion, Geom. Funct. Anal. 12 (2002) 380 MR1911665
87	J L Lions, Une construction d’espaces d’interpolation, C. R. Acad. Sci. Paris 251 (1960) 1853 MR119093
88	P Mankiewicz, On Lipschitz mappings between Fréchet spaces, Studia Math. 41 (1972) 225 MR308724
89	J Matoušek, Extension of Lipschitz mappings on metric trees, Comment. Math. Univ. Carolin. 31 (1990) 99 MR1056175
90	J Matoušek, Note on bi-Lipschitz embeddings into normed spaces, Comment. Math. Univ. Carolin. 33 (1992) 51 MR1173746
91	J Matoušek, On the distortion required for embedding finite metric spaces into normed spaces, Israel J. Math. 93 (1996) 333 MR1380650
92	J Matoušek, On embedding expanders into l_p spaces, Israel J. Math. 102 (1997) 189 MR1489105
93	J Matoušek, Lectures on discrete geometry, 212, Springer (2002) MR1899299
94	S Mazur, Une remarque sur l’homéomorphie des champs fonctionels, Studia Math. 1 (1929) 83
95	M Mendel, A Naor, Euclidean quotients of finite metric spaces, Adv. Math. 189 (2004) 451 MR2101227
96	M Mendel, A Naor, Metric cotype, Ann. of Math. 168 (2008) 247 MR2415403
97	M Mendel, A Naor, Markov convexity and local rigidity of distorted metrics, J. Eur. Math. Soc. 15 (2013) 287 MR2998836
98	M Mendel, A Naor, Spectral calculus and Lipschitz extension for barycentric metric spaces, Anal. Geom. Metr. Spaces 1 (2013) 163 MR3108872
99	M Mendel, A Naor, Nonlinear spectral calculus and super-expanders, Publ. Math. Inst. Hautes Études Sci. 119 (2014) 1 MR3210176
100	M Mendel, A Naor, Expanders with respect to Hadamard spaces and random graphs, Duke Math. J. 164 (2015) 1471 MR3352040
101	D Milman, On some criteria for the regularity of spaces of the type (B), C. R. (Dokl.) Acad. Sci. URSS 20 (1938) 243
102	J Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964) 275 MR161339
103	M Mimura, Sphere equivalence, Banach expanders, and extrapolation, Int. Math. Res. Not. 2015 (2015) 4372 MR3356758
104	G J Minty, On the extension of Lipschitz, Lipschitz–Hölder continuous, and monotone functions, Bull. Amer. Math. Soc. 76 (1970) 334 MR254575
105	A Naor, An introduction to the Ribe program, Japan. J. Math. 7 (2012) 167 MR2995229
106	A Naor, On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon–Roichman graphs, Combin. Probab. Comput. 21 (2012) 623 MR2942733
107	A Naor, Comparison of metric spectral gaps, Anal. Geom. Metr. Spaces 2 (2014) 1 MR3208067
108	A Naor, Uniform nonextendability from nets, C. R. Math. Acad. Sci. Paris 353 (2015) 991 MR3419848
109	A Naor, Discrete Riesz transforms and sharp metric X_p inequalities, Ann. of Math. 184 (2016) 991 MR3549628
110	A Naor, A spectral gap precludes low-dimensional embeddings, from: "33rd International Symposium on Computational Geometry" (editors B Aronov, M J Katz), Leibniz Int. Proc. Inform. 77, Schloss Dagstuhl (2017) MR3685722
111	A Naor, Metric dimension reduction : a snapshot of the Ribe program, from: "Proceedings of the International Congress of Mathematicians, I" (editors B Sirakov, P N de Souza, M Viana), World Sci. (2018) 759 MR3966745
112	A Naor, Y Peres, O Schramm, S Sheffield, Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces, Duke Math. J. 134 (2006) 165 MR2239346
113	A Naor, Y Rabani, On Lipschitz extension from finite subsets, Israel J. Math. 219 (2017) 115 MR3642017
114	A Naor, Y Rabani, A Sinclair, Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs, J. Funct. Anal. 227 (2005) 273 MR2168076
115	A Naor, G Schechtman, Metric X_p inequalities, Forum Math. Pi 4 (2016) MR3456183
116	A Naor, L Silberman, Poincaré inequalities, embeddings, and wild groups, Compos. Math. 147 (2011) 1546 MR2834732
117	I Newman, Y Rabinovich, Hard metrics from Cayley graphs of abelian groups, Theory Comput. 5 (2009) 125 MR2521347
118	E Odell, T Schlumprecht, The distortion problem, Acta Math. 173 (1994) 259 MR1301394
119	M I Ostrovskii, Metric embeddings: bilipschitz and coarse embeddings into Banach spaces, 49, de Gruyter (2013) MR3114782
120	N Ozawa, A note on non-amenability of ℬ(l_p) for p = 1,2, Int. J. Math. 15 (2004) 557 MR2078880
121	B J Pettis, A proof that every uniformly convex space is reflexive, Duke Math. J. 5 (1939) 249 MR1546121
122	G Pisier, Martingales with values in uniformly convex spaces, Israel J. Math. 20 (1975) 326 MR394135
123	G Pisier, Some applications of the complex interpolation method to Banach lattices, J. Analyse Math. 35 (1979) 264 MR555306
124	G Pisier, Complex interpolation between Hilbert, Banach and operator spaces, 978, Amer. Math. Soc. (2010) MR2732331
125	Y Rabinovich, On average distortion of embedding metrics into the line, Discrete Comput. Geom. 39 (2008) 720 MR2413155
126	Y Raynaud, On ultrapowers of non commutative L_p spaces, J. Operator Theory 48 (2002) 41 MR1926043
127	M Ribe, On uniformly homeomorphic normed spaces, Ark. Mat. 14 (1976) 237 MR440340
128	É Ricard, Hölder estimates for the noncommutative Mazur maps, Arch. Math. (Basel) 104 (2015) 37 MR3299148
129	M Riesz, Sur les maxima des formes bilinéaires et sur les fonctionnelles linéaires, Acta Math. 49 (1927) 465 MR1555250
130	T R Riley, Navigating in the Cayley graphs of SL_N(ℤ) and SL_N(𝔽_p), Geom. Dedicata 113 (2005) 215 MR2171306
131	I J Schoenberg, Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938) 522 MR1501980
132	E M Stein, Interpolation of linear operators, Trans. Amer. Math. Soc. 83 (1956) 482 MR82586
133	R Thom, Sur l’homologie des variétés algébriques réelles, from: "Differential and combinatorial topology" (editor S S Cairns), Princeton Univ. Press (1965) 255 MR0200942
134	G O Thorin, Convexity theorems generalizing those of M Riesz and Hadamard with some applications, Comm. Sém. Math. Univ. Lund 9 (1948) 1 MR25529
135	J H Wells, L R Williams, Embeddings and extensions in analysis, 84, Springer (1975) MR0461107