CaltechAUTHORS
  A Caltech Library Service

Metric Cotype

Mendel, Manor and Naor, Assaf (2006) Metric Cotype. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery , New York, pp. 79-88. ISBN 9780898716054. https://resolver.caltech.edu/CaltechAUTHORS:20101006-090230854

[img] PDF (Extended abstract) - Published Version
See Usage Policy.

606Kb
[img]
Preview
PDF (Complete text) - Published Version
See Usage Policy.

503Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20101006-090230854

Abstract

We introduce the notion of metric cotype, a property of metric spaces related to a property of normed spaces, called Rademacher cotype. Apart from settling a long standing open problem in metric geometry, this property is used to prove the following dichotomy: A family of metric spaces F is either almost universal (i.e., contains any finite metric space with any distortion > 1), or there exists α > 0, and arbitrarily large n-point metrics whose distortion when embedded in any member of F is at least Ω((log n)^α). The same property is also used to prove strong non-embeddability theorems of L_q into L_p, when q > max{2,p}. Finally we use metric cotype to obtain a new type of isoperimetric inequality on the discrete torus.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/math/0506201arXivUNSPECIFIED
http://dx.doi.org/10.1145/1109557.1109567DOIUNSPECIFIED
http://portal.acm.org/citation.cfm?id=1109567&CFID=111460922&CFTOKEN=19080344PublisherUNSPECIFIED
Additional Information:© 2006 Association for Computing Machinery. Extended abstract. A full version of this paper with all the details is available at http://arxiv.org/math.FA/0506201. We are grateful to Keith Ball for several valuable discussions. We thank Yuri Rabinovich for pointing out the connection to Matousek's BD Ramsey theorem. Comments from the SODA's referees helped in improving the presentation.
Subject Keywords:Computations in finite fields ; Geometrical problems and computations Computations on discrete structures ; Combinatorial algorithms
Record Number:CaltechAUTHORS:20101006-090230854
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20101006-090230854
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:20317
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:17 Nov 2010 20:16
Last Modified:03 Oct 2019 02:08

Repository Staff Only: item control page