×

An introduction to the Ribe program. (English) Zbl 1261.46013

Martin Ribe is a Swedish statistician who published very few, but highly influential papers on functional analysis in the 1970s. In his landmark work “On uniformly homeomorphic normed spaces” [I: Ark.Mat.14, 237–244 (1976; Zbl 0336.46018); II: ibid. 16, 1–9 (1978; Zbl 0389.46009)], he proved the following rigidity result. Suppose that \(X\) and \(Y\) are uniformly homeomorphic Banach spaces, i.e., there exists a (nonlinear) bijection \(\varphi: X\to Y\) such that \(\varphi\) and \(\varphi^{-1}\) are uniformly continuous. Then \(X\) and \(Y\) have the same finite dimensional subspaces, more precisely, \(X\) is (crudely) finitely representable in \(Y\) and vice versa. Hence, \(X\) and \(Y\) have the same (linear) local structure; for example, \(X\) has type \(p\) if and only if \(Y\) has type \(p\).
Consequently, every (linear) local property of a Banach space \(X\) should be possible to get encoded in purely metric terms of the metric space \(X\), forgetting its linear structure. The Ribe program asks for elucidating this correspondence, thus making it possible to study metric spaces by methods reminiscent of local Banach space theory. The first successful step was performed by J. Bourgain [Isr.J. Math.56, 222–230 (1986; Zbl 0643.46013)] who characterized superreflexive spaces along these lines. Many researchers, notably the author and his collaborators, have contributed to this research program, and the paper under review surveys and highlights some of these contributions and their applications. Whereas, for example, notions of nonlinear type of a metric space were suggested already 30 years ago by Enflo and Bourgain-Milman-Wolfson, the corresponding problem of nonlinear cotype was solved only recently by the author and M. Mendel [Ann.Math.(2) 168, No. 1, 247–298 (2008; Zbl 1187.46014)].
In particular, the author of this very interesting and well written survey discusses the following topics: metric type; metric cotype; Markov type and cotype; Markov convexity; Bourgain’s discretisation problem; nonlinear Dvoretzky type theorems. In the final section, he discusses applications: majorizing measures; Lipschitz maps onto cubes; approximate distance oracles and approximate rankings; random walks and quantitative non-embeddability.

MSC:

46B85 Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science
46B80 Nonlinear classification of Banach spaces; nonlinear quotients
46L07 Operator spaces and completely bounded maps
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aharoni I., Lindenstrauss J.: Uniform equivalence between Banach spaces. Bull. Amer. Math. Soc. 84, 281–283 (1978) · Zbl 0401.57026 · doi:10.1090/S0002-9904-1978-14475-9
[2] Aharoni I., Maurey B., Mityagin B.S.: Uniform embeddings of metric spaces and of Banach spaces into Hilbert spaces. Israel J. Math. 52, 251–265 (1985) · Zbl 0596.46010 · doi:10.1007/BF02786521
[3] Alon N., Milman V.D.: {\(\lambda\)}1, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38, 73–88 (1985) · Zbl 0549.05051 · doi:10.1016/0095-8956(85)90092-9
[4] Anderson R.D.: Hilbert space is homeomorphic to the countable infinite product of lines. Bull. Amer. Math. Soc. 72, 515–519 (1966) · Zbl 0137.09703 · doi:10.1090/S0002-9904-1966-11524-0
[5] A. Andoni, O. Neiman and A. Naor, Snowflake universality of Wasserstein spaces, preprint, 2010. · Zbl 1403.46020
[6] S. Arora, J.R. Lee and A. Naor, Euclidean distortion and the sparsest cut, J. Amer. Math. Soc., 21 (2008), 1–21 (electronic). · Zbl 1132.68070
[7] S. Arora, L. Lovász, I. Newman, Y. Rabani, Y. Rabinovich and S. Vempala, Local versus global properties of metric spaces (extended abstract), In: Proceedings of the Seventeenth Annual ACM–SIAM Symposium on Discrete Algorithms, ACM, New York, NY, 2006, pp. 41–50. · Zbl 1192.90155
[8] Arzhantseva G., Druţu C., Sapir M.: Compression functions of uniform embeddings of groups into Hilbert and Banach spaces. J. Reine Angew. Math. 633, 213–235 (2009) · Zbl 1258.20032
[9] Assouad P.: Plongements lipschitziens dans R n . Bull. Soc. Math. France 111, 429–448 (1983) · Zbl 0597.54015
[10] Y. Aumann and Y. Rabani, An O(log k) approximate min-cut max-flow theorem and approximation algorithm, SIAM J. Comput., 27 (1998), 291–301 (electronic). · Zbl 0910.05038
[11] Austin T.: Amenable groups with very poor compression into Lebesgue spaces. Duke Math. J. 159, 187–222 (2011) · Zbl 1226.43001 · doi:10.1215/00127094-1415860
[12] T. Austin and A. Naor, On the bi-Lipschitz structure of Wasserstein spaces, preprint, 2009.
[13] Austin T., Naor A., Peres Y.: The wreath product of $${\(\backslash\)mathbb{Z}}$$ with $${\(\backslash\)mathbb{Z}}$$ has Hilbert compression exponent $${\(\backslash\)frac{2}{3}}$$ . Proc. Amer. Math. Soc. 137, 85–90 (2009) · Zbl 1226.20032 · doi:10.1090/S0002-9939-08-09501-4
[14] Austin T., Naor A., Valette A.: The Euclidean distortion of the lamplighter group. Discrete Comput. Geom. 44, 55–74 (2010) · Zbl 1275.20044 · doi:10.1007/s00454-009-9162-6
[15] Ball K.: Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal. 2, 137–172 (1992) · Zbl 0788.46050 · doi:10.1007/BF01896971
[16] K. Ball, The Ribe Programme, Séminaire Bourbaki, 1047, 2012.
[17] Ball K., Carlen E.A., Lieb E.H.: Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math. 115, 463–482 (1994) · Zbl 0803.47037 · doi:10.1007/BF01231769
[18] S. Banach, Théorie des Opérations Linéaires, Monografie Matematyczne, 1, PWN–Polish Scientific Publishers, Warsaw, 1932. [Mathematical Monographs, 1].
[19] Y. Bartal, On approximating arbitrary metrices by tree metrics, In: STOC ’98, Dallas, TX, ACM, New York, NY, 1999, pp. 161–168.
[20] Bartal Y., Bollobás B., Mendel M.: Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. System Sci. 72, 890–921 (2006) · Zbl 1094.68114 · doi:10.1016/j.jcss.2005.05.008
[21] Bartal Y., Linial N., Mendel M., Naor A.: On metric Ramsey-type dichotomies. J. London Math. Soc. (2) 71, 289–303 (2005) · Zbl 1066.05142 · doi:10.1112/S0024610704006155
[22] Bartal Y., Linial N., Mendel M., Naor A.: On metric Ramsey-type phenomena. Ann. of Math. (2) 162, 643–709 (2005) · Zbl 1114.46007 · doi:10.4007/annals.2005.162.643
[23] Bartal Y., Linial N., Mendel M., Naor A.: Some low distortion metric Ramsey problems. Discrete Comput. Geom. 33, 27–41 (2005) · Zbl 1069.05050 · doi:10.1007/s00454-004-1100-z
[24] M.A. Bender and M. Farach-Colton, The LCA problem revisited, In: LATIN 2000: Theoretical Informatics, (eds. G.H. Gonnet, D. Panario and A. Viola), Lecture Notes in Comput. Sci., 1776, Springer-Verlag, 2000, pp. 88–94. · Zbl 0959.68133
[25] Y. Benyamini, The uniform classification of Banach spaces, In: Texas Functional Analysis Seminar 1984–1985, Austin, TX, Longhorn Notes, Univ. Texas Press, Austin, TX, 1985, pp. 15–38.
[26] Y. Benyamini and J. Lindenstrauss, Geometric Nonlinear Functional Analysis. Vol. 1, Amer. Math. Soc. Colloq. Publ., 48, Amer. Math. Soc., Providence, RI, 2000. · Zbl 0946.46002
[27] Bessaga C.: On topological classification of complete linear metric spaces. Fund. Math. 56, 251–288 (1964) · Zbl 0138.37404
[28] Bessaga C., Pełczyński A.: Some remarks on homeomorphisms of Banach spaces. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8, 757–761 (1960) · Zbl 0102.10001
[29] C. Bessaga and A. Pełczyński, Selected Topics in Infinite-Dimensional Topology, Monografie Matematyczne, 58, PWN–Polish Scientific Publishers, Warsaw, 1975. [Mathematical Monographs, 58].
[30] A. Blum, H. Karloff, Y. Rabani and M. Saks, A decomposition theorem for task systems and bounds for randomized server problems, SIAM J. Comput., 30 (2000), 1624–1661 (electronic). · Zbl 0977.68039
[31] Bourgain J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math. 52, 46–52 (1985) · Zbl 0657.46013 · doi:10.1007/BF02776078
[32] Bourgain J.: The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math. 56, 222–230 (1986) · Zbl 0643.46013 · doi:10.1007/BF02766125
[33] J. Bourgain, Remarks on the extension of Lipschitz maps defined on discrete sets and uniform homeomorphisms, In: Geometrical Aspects of Functional Analysis (1985/86), Lecture Notes in Math., 1267, Springer-Verlag, 1987, pp. 157–167.
[34] Bourgain J., Figiel T., Milman V.D.: On Hilbertian subsets of finite metric spaces. Israel J. Math. 55, 147–152 (1986) · Zbl 0634.46008 · doi:10.1007/BF02801990
[35] Bourgain J., Milman V.D., Wolfson H.: On type of metric spaces. Trans. Amer. Math. Soc. 294, 295–317 (1986) · Zbl 0617.46024 · doi:10.1090/S0002-9947-1986-0819949-8
[36] M.R. Bridson and A. Haefliger, Metric Spaces of Non-Positive Curvature, Grundlehren Math. Wiss., 319, Springer-Verlag, 1999. · Zbl 0988.53001
[37] B. Brinkman, A. Karagiozova and J.R. Lee, Vertex cuts, random walks, and dimension reduction in series-parallel graphs, In: STOC ’07–Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, NY, 2007, pp. 621–630. · Zbl 1232.68163
[38] M. Charikar and A. Karagiozova, A tight threshold for metric Ramsey phenomena, In: Proceedings of the Sixteenth Annual ACM–SIAM Symposium on Discrete Algorithms, ACM, New York, NY, 2005, pp. 129–136 (electronic). · Zbl 1297.05236
[39] M. Charikar, K. Makarychev and Y. Makarychev, Local global tradeoffs in metric embeddings, In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), IEEE Computer Soc., Los Alamitos, CA, 2007, pp. 713–723. · Zbl 1206.68138
[40] J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, In: Problems in Analysis (Papers Dedicated to Salomon Bochner, 1969), Princeton Univ. Press, Princeton, NJ, 1970, pp. 195–199.
[41] Cheeger J., Kleiner B.: Differentiating maps into L 1, and the geometry of BV functions. Ann. of Math. (2) 171, 1347–1385 (2010) · Zbl 1194.22009 · doi:10.4007/annals.2010.171.1347
[42] P.-A. Cherix, M. Cowling, P. Jolissaint, P. Julg and A. Valette, Groups with the Haagerup Property. Gromov’s a-T-menability, Progr. Math., 197, Birkhäuser Verlag, Basel, 2001. · Zbl 1030.43002
[43] Christ M., (1990) A T(b) theorem with remarks on analytic capacity and the Cauchy integral, Colloq. Math., 60/61, 601–628 · Zbl 0758.42009
[44] H. Corson and V. Klee, Topological classification of convex sets, In: Proc. Sympos. Pure Math., 7, Amer. Math. Soc., Providence, RI, 1963, pp. 37–51. · Zbl 0207.42901
[45] de Cornulier Y., Tessera R., Valette A.: Isometric group actions on Hilbert spaces: growth of cocycles. Geom. Funct. Anal. 17, 770–792 (2007) · Zbl 1129.22004 · doi:10.1007/s00039-007-0604-0
[46] P. de la Harpe, Topics in Geometric Group Theory, Chicago Lectures in Math., Univ. of Chicago Press, Chicago, IL, 2000. · Zbl 0965.20025
[47] A. Dvoretzky, Some results on convex bodies and Banach spaces, In: Proc. Internat. Sympos. Linear Spaces, Jerusalem, 1960, Jerusalem Academic Press, Jerusalem, 1961, pp. 123–160.
[48] Enflo P.: On a problem of Smirnov. Ark. Mat. 8, 107–109 (1969) · Zbl 0196.14003 · doi:10.1007/BF02589550
[49] Enflo P.: On the nonexistence of uniform homeomorphisms between L p -spaces. Ark. Mat. 8, 103–105 (1969) · Zbl 0196.14002 · doi:10.1007/BF02589549
[50] P. Enflo, Uniform structures and square roots in topological groups. I, II, Israel J. Math., 8 (1970), 230–252; ibid., 8 (1970), 253–272. · Zbl 0214.28402
[51] Enflo P.: Banach spaces which can be given an equivalent uniformly convex norm. Israel J. Math. 13, 281–288 (1972) · Zbl 0259.46012 · doi:10.1007/BF02762802
[52] P. Enflo, Uniform homeomorphisms between Banach spaces, In: Séminaire Maurey–Schwartz (1975–1976), Espaces, L p , Applications Radonifiantes et Géométriedes Espaces de Banach, Exp. No. 18, Centre Math., École Polytech., Palaiseau, 1976, 7 pp. · Zbl 0339.46009
[53] P. Erdos, Extremal problems in graph theory, In: Theory of Graphs and its Applications, Proc. Sympos. Smolenice, 1963, Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 29–36.
[54] A.G. Èrschler, On the asymptotics of the rate of departure to infinity, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 6, 283 (2001), 251–257, 263.
[55] M. Fabian, P. Habala, P. Hájek, V. Montesinos Santalucía, J. Pelant and V. Zizler, Functional Analysis and Infinite-Dimensional Geometry, CMS Books Math./Ouvrages Math. SMC, 8, Springer-Verlag, 2001. · Zbl 0981.46001
[56] Fakcharoenphol J., Rao S., Talwar K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci. 69, 485–497 (2004) · Zbl 1071.68082 · doi:10.1016/j.jcss.2004.04.011
[57] X. Fernique, Regularité des trajectoires des fonctions aléatoires gaussiennes, In: École d’Été de Probabilités de Saint-Flour, IV-1974, Lecture Notes in Math., 480, Springer-Verlag, 1975, pp. 1–96.
[58] X. Fernique, Évaluations de processus gaussiens composés, In: Probability in Banach spaces, Proc. First Internat. Conf., Oberwolfach, 1975, Lecture Notes in Math., 526, Springer-Verlag, 1976, pp. 67–83.
[59] X. Fernique, Caractérisation de processus à trajectoires majorées ou continues, In: Séminaire de Probabilités, XII, Univ. Strasbourg, Strasbourg, 1976/1977, Lecture Notes in Math., 649, Springer-Verlag, 1978, pp. 691–706.
[60] Figiel T.: On nonlinear isometric embeddings of normed linear spaces. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 16, 185–188 (1968) · Zbl 0155.18301
[61] Figiel T., Lindenstrauss J., Milman V.D.: The dimension of almost spherical sections of convex bodies. Acta Math. 139, 53–94 (1977) · Zbl 0375.52002 · doi:10.1007/BF02392234
[62] M. Fréchet, Les Espaces Abstraits et leur Théorie Considérée comme Introduction à L’analyse Générale, Collection de Monographies sur la Théorie des Fonctions, Gauthier-Villars, Paris, 12, 1928, 296 pp.
[63] Giladi O., Mendel M., Naor A.: Improved bounds in the metric cotype inequality for Banach spaces. J. Funct. Anal. 260, 164–194 (2011) · Zbl 1218.46012 · doi:10.1016/j.jfa.2010.08.015
[64] O. Giladi, A. Naor and G. Schechtman, Bourgain’s discretization theorem, preprint, arXiv:1110.5368; Ann. Fac. Sci. Toulouse Math., to appear (2011).
[65] Gorelik E.: The uniform nonequivalence of L p and l p . Israel J. Math. 87, 1–8 (1994) · Zbl 0819.46013 · doi:10.1007/BF02772978
[66] Gromov M.: Volume and bounded cohomology. Inst. Hautes Études Sci. Publ. Math. 56, 5–99 (1982) · Zbl 0516.53046
[67] Gromov M.: Filling Riemannian manifolds. J. Differential Geom. 18, 1–147 (1983) · Zbl 0515.53037
[68] M. Gromov, Asymptotic invariants of infinite groups, In: Geometric Group Theory. Vol. 2, Sussex, 1991, London Math. Soc. Lecture Note Ser., 182, Cambridge Univ. Press, Cambridge, 1993, pp. 1–295. · Zbl 0841.20039
[69] M. Gromov, Metric Structures for Riemannian and Non-Riemannian Spaces, Based on the 1981 French original, With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean Michael Bates, Mod. Birkhäuser Class., Birkhäuser Boston Inc., Boston, MA, English ed., 2007. · Zbl 1113.53001
[70] Grothendieck A.: Sur certaines classes de suites dans les espaces de Banach et le théorème de Dvoretzky–Rogers. Bol. Soc. Mat. São Paulo 8, 81–110 (1953)
[71] A. Grothendieck, Erratum au mémoire: Produits tensoriels topologiques et espaces nucléaires, Ann. Inst. Fourier (Grenoble), 6 (1955–1956), 117–120. · Zbl 0072.12003
[72] Guentner E., Kaminker J.: Exactness and uniform embeddability of discrete groups. J. London Math. Soc. (2) 70, 703–718 (2004) · Zbl 1082.46049 · doi:10.1112/S0024610704005897
[73] Gupta A., Newman I., Rabinovich Y., Sinclair A.: Cuts, trees and l 1-embeddings of graphs. Combinatorica 24, 233–269 (2004) · Zbl 1056.05040 · doi:10.1007/s00493-004-0015-x
[74] Hanner O.: On the uniform convexity of L p and l p . Ark. Mat. 3, 239–244 (1956) · Zbl 0071.32801 · doi:10.1007/BF02589410
[75] S. Har-Peled and M. Mendel, Fast construction of nets in low-dimensional metrics and their applications, SIAM J. Comput., 35 (2006), 1148–1184 (electronic). · Zbl 1100.68014
[76] Harel D., Tarjan R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13, 338–355 (1984) · Zbl 0535.68022 · doi:10.1137/0213024
[77] Heinrich S., Mankiewicz P.: Applications of ultrapowers to the uniform and Lipschitz classification of Banach spaces. Studia Math. 73, 225–251 (1982) · Zbl 0506.46008
[78] Henkin G.M.: The lack of a uniform homeomorphism between the spaces of smooth functions of one and of n variables $${(n \(\backslash\)geq 2)}$$ . Mat. Sb. (N.S.) 74, 595–607 (1967) · Zbl 0155.18501
[79] S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.), 43 (2006), 439–561 (electronic). · Zbl 1147.68608
[80] Howroyd J.D.: On dimension and on the existence of sets of finite positive Hausdorff measure. Proc. London Math. Soc. (3) 70, 581–604 (1995) · Zbl 0828.28002 · doi:10.1112/plms/s3-70.3.581
[81] Hughes B.: Trees and ultrametric spaces: a categorical equivalence. Adv. Math. 189, 148–191 (2004) · Zbl 1061.57021 · doi:10.1016/j.aim.2003.11.008
[82] T. Hytönen, S. Li and A. Naor, Quantitative affine approximation for UMD targets, preprint, 2012.
[83] T. Hytönen and A. Naor, Pisier’s inequality revisited, preprint, 2012.
[84] R.C. James, Some self-dual properties of normed linear spaces, In: Symposium on Infinite-Dimensional Topology, Louisiana State Univ., Baton Rouge, LA, 1967, Ann. of Math. Stud., 69, Princeton Univ. Press, Princeton, NJ, 1972, pp. 159–175.
[85] James R.C.: Super-reflexive Banach spaces. Canad. J. Math. 24, 896–904 (1972) · Zbl 0222.46009 · doi:10.4153/CJM-1972-089-7
[86] James R.C.: Nonreflexive spaces of type 2. Israel J. Math. 30, 1–13 (1978) · Zbl 0384.46004 · doi:10.1007/BF02760825
[87] F. John, Extremum problems with inequalities as subsidiary conditions, In: Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, Interscience Publishers, Inc., New York, NY, 1948, pp. 187–204.
[88] W.B. Johnson and J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, In: Conference in Modern Analysis and Probability, New Haven, CN, 1982, Contemp. Math., 26, Amer. Math. Soc., Providence, RI, 1984, pp. 189–206. · Zbl 0539.46017
[89] Johnson W.B., Lindenstrauss J., Schechtman G.: Banach spaces determined by their uniform structures. Geom. Funct. Anal. 6, 430–470 (1996) · Zbl 0864.46008 · doi:10.1007/BF02249259
[90] Johnson W.B., Schechtman G.: Diamond graphs and super-reflexivity. J. Topol. Anal. 1, 177–189 (2009) · Zbl 1183.46022 · doi:10.1142/S1793525309000114
[91] M.Ĭ. Kadec’, On strong and weak convergence, Dokl. Akad. Nauk SSSR, 122 (1958), 13–16. · Zbl 0086.09204
[92] M.Ĭ. Kadec’, Topological equivalence of all separable Banach spaces, Dokl. Akad. Nauk SSSR, 167 (1966), 23–25.
[93] M.Ĭ. Kadec’, A proof of the topological equivalence of all separable infinite-dimensional Banach spaces, Funkcional. Anal. i Priložen., 1 (1967), 61–70. · Zbl 0166.10603
[94] Kahane J.-P.: Sur les sommes vectorielles $${\(\backslash\)sum \(\backslash\)pm u_{n}}$$ . C. R. Acad. Sci. Paris 259, 2577– (1964)
[95] N.J. Kalton, The uniform structure of Banach spaces, Math. Ann., to appear (2011). · Zbl 1220.46014
[96] Kalton N.J.: The nonlinear geometry of Banach spaces. Rev. Mat. Complut. 21, 7–60 (2008) · Zbl 1156.46003
[97] Karloff H., Rabani Y., Ravid Y.: Lower bounds for randomized k-server and motion-planning algorithms. SIAM J. Comput. 23, 293–312 (1994) · Zbl 0804.68066 · doi:10.1137/S0097539792224838
[98] T. Keleti, A. Máthé and O. Zindulka, Hausdorff dimension of metric spaces and Lipschitz maps onto cubes, preprint, arXiv:1203.0686. · Zbl 1296.28008
[99] Khot S., Naor A.: Nonembeddability theorems via Fourier analysis. Math. Ann. 334, 821–852 (2006) · Zbl 1102.46051 · doi:10.1007/s00208-005-0745-0
[100] S. Khot and R. Saket, SDP integrality gaps with local $${\(\backslash\)ell_1}$$ -embeddability, In: 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 565–574.
[101] Laakso T.J.: Plane with A weighted metric not bi-Lipschitz embeddable to $${\(\backslash\)mathbb{R}\^{N}}$$ . Bull. London Math. Soc. 34, 667–676 (2002) · Zbl 1029.30014 · doi:10.1112/S0024609302001200
[102] Lang U., Plaut C.: Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata 87, 285–307 (2001) · Zbl 1024.54013 · doi:10.1023/A:1012093209450
[103] M. Ledoux and M. Talagrand, Probability in Banach Spaces. Isoperimetry and Processes, Ergeb. Math. Grenzgeb. (3), 23, Springer-Verlag, 1991. · Zbl 0748.60004
[104] Lee J.R., Naor A., Peres Y.: Trees and Markov convexity. Geom. Funct. Anal. 18, 1609–1659 (2009) · Zbl 1171.05318 · doi:10.1007/s00039-008-0689-0
[105] S. Li and A. Naor, Discretization and affine approximation in high dimensions, preprint, arXiv:1202.2567; Israel J. Math., to appear (2012).
[106] Lindenstrauss J.: On the modulus of smoothness and divergent series in Banach spaces. Michigan Math. J. 10, 241–252 (1963) · doi:10.1307/mmj/1028998906
[107] Lindenstrauss J.: On nonlinear projections in Banach spaces. Michigan Math. J. 11, 263–287 (1964) · Zbl 0195.42803 · doi:10.1307/mmj/1028999141
[108] Lindenstrauss J.: Some aspects of the theory of Banach spaces. Advances in Math. 5, 159–180 (1970) · Zbl 0203.12002 · doi:10.1016/0001-8708(70)90032-0
[109] J. Lindenstrauss, Uniform embeddings, homeomorphisms and quotient maps between Banach spaces (a short survey), In: 8th Prague Topological Symposium on General Topology and Its Relations to Modern Analysis and Algebra, 1996, Topology Appl., 85, Elsevier Sci. B. V., Amsterdam, 1998, pp. 265–279. · Zbl 0929.46017
[110] N. Linial, Finite metric-spaces–combinatorics, geometry and algorithms, In: Proceedings of the International Congress of Mathematicians, 3, Beijing, 2002, Higher Ed. Press, Beijing, 2002, pp. 573–586. · Zbl 0997.05019
[111] Linial N., London E., Rabinovich Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 215–245 (1995) · Zbl 0827.05021 · doi:10.1007/BF01200757
[112] Linial N., Magen A., Naor A.: Girth and Euclidean distortion. Geom. Funct. Anal. 12, 380–394 (2002) · Zbl 0991.05037 · doi:10.1007/s00039-002-8251-y
[113] Linial N., Saks M.: The Euclidean distortion of complete binary trees. Discrete Comput. Geom. 29, 19–21 (2003) · Zbl 1008.05040 · doi:10.1007/s00454-002-2827-z
[114] K. Makarychev and Y. Makarychev, Metric extension operators, vertex sparsifiers and Lipschitz extendability, In: 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), IEEE Computer Soc., Los Alamitos, CA, 2010, pp. 255–264. · Zbl 1341.05104
[115] Marcus M.B., Pisier G.: Characterizations of almost surely continuous p-stable random Fourier series and strongly stationary processes. Acta Math. 152, 245–301 (1984) · Zbl 0547.60047 · doi:10.1007/BF02392199
[116] Matoušek J.: Ramsey-like properties for bi-Lipschitz mappings of finite metric spaces. Comment. Math. Univ. Carolin. 33, 451–463 (1992) · Zbl 0769.05093
[117] Matoušek J.: On embedding trees into uniformly convex Banach spaces. Israel J. Math. 114, 221–237 (1999) · Zbl 0948.46011 · doi:10.1007/BF02785579
[118] J. Matoušek, Lectures on Discrete Geometry, Grad. Texts in Math., 212, Springer-Verlag, 2002.
[119] P. Mattila, Geometry of Sets and Measures in Euclidean Spaces. Fractals and Rectifiability, Cambridge Stud. Adv. Math., 44, Cambridge Univ. Press, Cambridge, 1995. · Zbl 0819.28004
[120] B. Maurey, Théorèmes de Factorisation pour les Opérateurs Linéaires à Valeurs dans les Espaces L p , With an English summary, Astérisque, 11, Soc. Math. France, Paris, 1974.
[121] B. Maurey, Type, cotype and K-convexity, In: Handbook of the Geometry of Banach Spaces, 2, North-Holland, Amsterdam, 2003, pp. 1299–1332.
[122] Maurey B., Pisier G.: Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach. Studia Math. 58, 45–90 (1976) · Zbl 0344.47014
[123] Mazur S., Ulam S.: Sur les transformations isométriques d’espaces vectoriels normés. C. R. Math. Acad. Sci. Paris 194, 946–948 (1932) · Zbl 0004.02103
[124] M. Mendel, Metric dichotomies, In: Limits of Graphs in Group Theory and Computer Science, EPFL Press, Lausanne, 2009, pp. 59–76.
[125] Mendel M., Naor A.: Euclidean quotients of finite metric spaces. Adv. Math. 189, 451–494 (2004) · Zbl 1088.46007 · doi:10.1016/j.aim.2003.12.001
[126] M. Mendel and A. Naor, Some applications of Ball’s extension theorem, Proc. Amer. Math. Soc., 134 (2006), 2577–2584 (electronic). · Zbl 1108.46052
[127] Mendel M., Naor A.: Ramsey partitions and proximity data structures. J. Eur. Math. Soc. (JEMS) 9, 253–275 (2007) · Zbl 1122.68043 · doi:10.4171/JEMS/79
[128] Mendel M., Naor A.: Scaled Enflo type is equivalent to Rademacher type. Bull. Lond. Math. Soc. 39, 493–498 (2007) · Zbl 1126.46008 · doi:10.1112/blms/bdm016
[129] M. Mendel and A. Naor, Markov convexity and local rigidity of distorted metrics [extended abstract], In: Computational Geometry (SCG ’08), ACM, New York, NY, 2008, pp. 49–58; Full version, J. Eur. Math. Soc. (JEMS), to appear. · Zbl 1192.52010
[130] Mendel M., Naor A.: Metric cotype. Ann. of Math. (2) 168, 247–298 (2008) · Zbl 1187.46014 · doi:10.4007/annals.2008.168.247
[131] Mendel M., Naor A.: Maximum gradient embeddings and monotone clustering. Combinatorica 30, 581–615 (2010) · Zbl 1274.30176 · doi:10.1007/s00493-010-2302-z
[132] M. Mendel and A. Naor, Towards a calculus for non-linear spectral gaps, In: Proceedings of the Twenty-First Annual ACM–SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2010, pp. 236–255. · Zbl 1288.05063
[133] A. Andoni, O. Neiman and A. Naor, Snowflake universality of Wasserstein spaces, preprint, 2010. · Zbl 1403.46020
[134] M. Mendel and A. Naor, Ultrametric skeletons, preprint, arXiv:1112.3416; Proc. Natl. Acad. Sci. USA, to appear (2011).
[135] M. Mendel and A. Naor, Spectral calculus and Lipschitz extension for barycentric metric spaces, preprint, 2012. · Zbl 1297.54037
[136] M. Mendel and A. Naor, Ultrametric subsets with large Hausdorff dimension, Invent. Math., DOI: 10.1007/s00222-012-0402-7 , 2012. · Zbl 1272.30082
[137] M. Mendel and C. Schwob, Fast C-K-R partitions of sparse graphs, Chic. J. Theoret. Comput. Sci., 2009 (2009), Article 2, 15 pp. · Zbl 1286.68373
[138] V.D. Milman, A new proof of A. Dvoretzky’s theorem on cross-sections of convex bodies, Funkcional. Anal. i Priložen., 5 (1971), 28–37.
[139] Milman V.D.: Almost Euclidean quotient spaces of subspaces of a finite-dimensional normed space. Proc. Amer. Math. Soc. 94, 445–449 (1985) · Zbl 0581.46014 · doi:10.1090/S0002-9939-1985-0787891-1
[140] V.D. Milman and G. Schechtman, An ”isomorphic” version of Dvoretzky’s theorem. II, In: Convex Geometric Analysis, Berkeley, CA, 1996, Math. Sci. Res. Inst. Publ., 34, Cambridge Univ. Press, Cambridge, 1999, pp. 159–164. · Zbl 0942.46012
[141] Milnor J., Thurston W.: Characteristic numbers of 3-manifolds. Enseignement Math. (2) 23, 249–254 (1977) · Zbl 0393.57002
[142] P.B. Miltersen, Cell probe complexity–a survey, In: 19th Conference on the Foundations of Software Technology and Theoretical Computer Science, 1999.
[143] Mostow G.D.: Quasi-conformal mappings in n-space and the rigidity of hyperbolic space forms. Inst. Hautes Études Sci. Publ. Math. 34, 53–104 (1968) · Zbl 0189.09402 · doi:10.1007/BF02684590
[144] Naor A.: A phase transition phenomenon between the isometric and isomorphic extension problems for Hölder functions between L p spaces. Mathematika 48, 253–271 (2001) · Zbl 1059.46059 · doi:10.1112/S0025579300014480
[145] A. Naor, An application of metric cotype to quasisymmetric embeddings, preprint, arXiv:math/0607644.
[146] A. Naor, L 1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry, In: Proceedings of the International Congress of Mathematicians, 3, Hindustan Book Agency, New Delhi, 2010, pp. 1549–1575. · Zbl 1232.46021
[147] A. Naor and Y. Peres, Embeddings of discrete groups and the speed of random walks, Int. Math. Res. Not. IMRN, 2008 (2008), Art. ID rnn 076, 34 pp. · Zbl 1163.46007
[148] Naor A., Peres Y.: L p compression, traveling salesmen, and stable walks. Duke Math. J. 157, 53–108 (2011) · Zbl 1268.20044 · doi:10.1215/00127094-2011-002
[149] Naor A., Peres Y., Schramm O., Sheffield S.: Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces. Duke Math. J. 134, 165–197 (2006) · Zbl 1108.46012 · doi:10.1215/S0012-7094-06-13415-4
[150] Naor A., Schechtman G.: Remarks on non linear type and Pisier’s inequality. J. Reine Angew. Math. 552, 213–236 (2002) · Zbl 1033.46013
[151] Naor A., Tao T.: Random martingales and localization of maximal inequalities. J. Funct. Anal. 259, 731–779 (2010) · Zbl 1196.42018 · doi:10.1016/j.jfa.2009.12.009
[152] A. Naor and T. Tao, Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem, preprint, arXiv:1003.4013; Israel J. Math., to appear (2010).
[153] Nazarov F., Treil S., Volberg A.: The Tb-theorem on non-homogeneous spaces. Acta Math. 190, 151–239 (2003) · Zbl 1065.42014 · doi:10.1007/BF02392690
[154] Ohta S.-I.: Markov type of Alexandrov spaces of non-negative curvature. Mathematika 55, 177–189 (2009) · Zbl 1195.46019 · doi:10.1112/S0025579300001005
[155] A. Olshanskii and D. Osin, A quasi-isometric embedding theorem for groups, preprint, arXiv:1202.6437. · Zbl 1331.20054
[156] Ostrovskii M.I.: On metric characterizations of some classes of Banach spaces. C. R. Acad. Bulgare Sci. 64, 775–784 (2011) · Zbl 1289.46038
[157] M.I. Ostrovskii, Different forms of metric characterizations of classes of Banach spaces, preprint, arXiv:1112.0801. · Zbl 1319.46017
[158] Ostrovskii M.I.: Low-distortion embeddings of graphs with large girth. J. Funct. Anal. 262, 3548–3555 (2012) · Zbl 1244.46036 · doi:10.1016/j.jfa.2012.01.020
[159] M.I. Ostrovskii, Test-space characterizations of some classes of Banach spaces, preprint, arXiv:1112.3086. · Zbl 1325.46023
[160] Pansu P.: Métriques de Carnot–Carathéodory et quasiisométries des espaces symétriques de rang un, Ann. of Math. 129(2), 1–60 (1989) · Zbl 0678.53042
[161] Pisier G.: Sur les espaces de Banach qui ne contiennent pas uniformément de $${l\^{1}_{n}}$$ . C. R. Acad. Sci. Paris Sér. A-B 277, A991–A994 (1973) · Zbl 0271.46011
[162] Pisier G.: with values in uniformly convex spaces. Israel J. Math. 20, 326–350 (1975) · Zbl 0344.46030 · doi:10.1007/BF02760337
[163] Pisier G.: Holomorphic semigroups and the geometry of Banach spaces. Ann. of Math. 115(2), 375–392 (1982) · Zbl 0487.46008 · doi:10.2307/1971396
[164] G. Pisier, Probabilistic methods in the geometry of Banach spaces, In: Probability and Analysis, Varenna, 1985, Lecture Notes in Math., 1206, Springer-Verlag, 1986, pp. 167–241.
[165] G. Pisier and Q.H. Xu, Random series in the real interpolation spaces between the spaces v p , In: Geometrical Aspects of Functional Analysis, Israel Seminar, 1985–1986, Lecture Notes in Math., 1267, Springer-Verlag, 1987, pp. 185–209.
[166] Rabinovich Y.: On average distortion of embedding metrics into the line. Discrete Comput. Geom. 39, 720–733 (2008) · Zbl 1158.68050 · doi:10.1007/s00454-007-9047-5
[167] P. Raghavendra and D. Steurer, Integrality gaps for strong SDP relaxations of unique games, In: 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 575–585. · Zbl 1292.90230
[168] Revelle D.: Rate of escape of random walks on wreath products and related groups. Ann. Probab. 31, 1917–1934 (2003) · Zbl 1051.60047 · doi:10.1214/aop/1068646371
[169] Ribe M.: On uniformly homeomorphic normed spaces. Ark. Mat. 14, 237–244 (1976) · Zbl 0336.46018 · doi:10.1007/BF02385837
[170] Ribe M.: On uniformly homeomorphic normed spaces. II, Ark. Mat. 16, 1–9 (1978) · Zbl 0389.46009 · doi:10.1007/BF02385979
[171] Ribe M.: Existence of separable uniformly homeomorphic nonisomorphic Banach spaces. Israel J. Math. 48, 139–147 (1984) · Zbl 0577.46015 · doi:10.1007/BF02761159
[172] Sachs H.: Regular graphs with given girth and restricted circuits. J. London Math. Soc. 38, 423–429 (1963) · Zbl 0117.17302 · doi:10.1112/jlms/s1-38.1.423
[173] Sagan H.: Space-Filling Curves. Springer-Verlag, Universitext (1994) · Zbl 0806.01019
[174] Schechtman G.: Two observations regarding embedding subsets of Euclidean spaces in normed spaces. Adv. Math. 200, 125–135 (2006) · Zbl 1108.46011 · doi:10.1016/j.aim.2004.11.003
[175] Semmes S.: On the nonexistence of bi-Lipschitz parameterizations and geometric problems about A weights. Rev. Mat. Iberoamericana 12, 337–410 (1996) · Zbl 0858.46017 · doi:10.4171/RMI/201
[176] Solé P.: The second eigenvalue of regular graphs of given girth. J. Combin. Theory Ser. B 56, 239–249 (1992) · Zbl 0761.05070 · doi:10.1016/0095-8956(92)90020-X
[177] C. Sommer, E. Verbin and W. Yu, Distance oracles for sparse graphs, In: 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), IEEE Computer Soc., Los Alamitos, CA, 2009, pp. 703–712. · Zbl 1292.05253
[178] Talagrand M.: Regularity of Gaussian processes. Acta Math. 159, 99–149 (1987) · Zbl 0712.60044 · doi:10.1007/BF02392556
[179] Talagrand M.: Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph connectivity theorem. Geom. Funct. Anal. 3, 295–314 (1993) · Zbl 0806.46035 · doi:10.1007/BF01895691
[180] M. Talagrand The Generic Chaining. Upper and Lower Bounds of Stochastic Processes, Springer Monogr. Math., Springer-Verlag, 2005. · Zbl 1075.60001
[181] M. Talagrand, Upper and Lower Bounds for Stochastic Processes, Modern Methods and Classical Problems, forthcoming book. · Zbl 1293.60001
[182] M. Thorup and U. Zwick, Approximate distance oracles, J. ACM, 52 (2005), 1–24 (electronic). · Zbl 1175.68303
[183] Toruńczyk H.: Characterizing Hilbert space topology. Fund. Math. 111, 247–262 (1981) · Zbl 0468.57015
[184] Urbański M.: Transfinite Hausdorff dimension. Topology Appl. 156, 2762–2771 (2009) · Zbl 1181.54040 · doi:10.1016/j.topol.2009.01.025
[185] J. Väisälä, The free quasiworld. Freely quasiconformal and related maps in Banach spaces, In: Quasiconformal Geometry and Dynamics, Lublin, 1996, Banach Center Publ., 48, Polish Acad. Sci., Warsaw, 1999, pp. 55–118. · Zbl 0934.30018
[186] Vestfrid I.A., Timan A.F.: A universality property of Hilbert spaces, Dokl. Akad. Nauk SSSR. 246, 528–530 (1979) · Zbl 0423.54007
[187] C. Villani, Topics in Optimal Transportation, Grad. Stud. Math., 58, Amer. Math. Soc., Providence, RI, 2003. · Zbl 1106.90001
[188] R. Wagner, Notes on an inequality by Pisier for functions on the discrete cube, In: Geometric Aspects of Functional Analysis, Lecture Notes in Math., 1745, Springer-Verlag, 2000, pp. 263–268. · Zbl 0981.46021
[189] Williamson D.P., Shmoys D.B.: The Design of Approximation Algorithms. Cambridge Univ. Press, Cambridge (2011) · Zbl 1219.90004
[190] Wojtaszczyk P., Banach Spaces for Analysts, Cambridge Stud. Adv. Math., 25, Cambridge Univ. Press, Cambridge, 1991. · Zbl 0724.46012
[191] Wulff-Nilsen C. Approximate distance oracles with improved query time, preprint, arXiv:1202.2336. · Zbl 1412.68091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.