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.

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

PDF (Complete text) - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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
Additional Information:© 2006 Association for Computing Machinery. Extended abstract. A full version of this paper with all the details is available at 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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:20317
Deposited By: Tony Diaz
Deposited On:17 Nov 2010 20:16
Last Modified:08 Nov 2021 23:58

Repository Staff Only: item control page