## תקציר

We study the metric properties of finite subsets of L_{1}. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weighted graphs, including the Sparsest Cut Problem, one of the most compelling open problems in the field of approximation. Additionally, many open questions in geometric non-linear functional analysis involve the properties of finite subsets of L_{1}. We present some new observations concerning the relation of L_{1} to dimension, topology, and Euclidean distortion. We show that every n-point subset of L_{1} embeds into L_{2} with average distortion O(√log n), yielding the first evidence that the conjectured worst-case bound of O(√log n) is valid. We also address the issue of dimension reduction in L_{p} for p ∈(1,2). We resolve a question left open in [1] about the impossibility of linear dimension reduction in the above cases, and we show that the example of [2,3] cannot be used to prove a lower bound for the non-linear case. This is accomplished by exhibiting constant-distortion embeddings of snowflaked planar metrics into Euclidean space.

שפה מקורית | אנגלית |
---|---|

כותר פרסום המארח | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

עורכים | Martin Farach-Colton |

מוציא לאור | Springer Verlag |

עמודים | 401-412 |

מספר עמודים | 12 |

מסת"ב (מודפס) | 3540212582, 9783540212584 |

מזהי עצם דיגיטלי (DOIs) | |

סטטוס פרסום | פורסם - 2004 |

פורסם באופן חיצוני | כן |

### סדרות פרסומים

שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

כרך | 2976 |

ISSN (מודפס) | 0302-9743 |

ISSN (אלקטרוני) | 1611-3349 |

## טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Metric structures in L_{1}: Dimension, snowflakes, and average distortion'. יחד הם יוצרים טביעת אצבע ייחודית.