Vi studerar de metriska egenskaperna hos ändliga undergrupper av L1. Analysen av sådana mätvärden är central för ett antal viktiga algoritmiska problem som involverar skärstrukturen hos viktade grafer, inklusive det glesaste skärproblemet, ett av de mest övertygande öppna problemen inom området approximationsalgoritmer. Dessutom omfattar många öppna frågor i geometrisk icke-linjär funktionsanalys egenskaperna hos finita undergrupper av L1. Vi presenterar några nya observationer om förhållandet mellan L1 och dimension, topologi och Euclidean distorsion. Vi visar att varje n-punkt delmängd av L1 inbäddar i L2 med genomsnittlig distorsion O( ε log n), vilket ger det första beviset för att det förmodade värsta fallet som är bundet av O( ε log n) är giltigt. Vi tar också upp frågan om dimensionsminskning i Lp för p  på (1, 2). Vi löser en fråga som lämnades öppen [4] om omöjligheten av linjär dimensionsminskning i ovanstående fall, och vi visar att exemplet [3, 16] inte kan användas för att bevisa en lägre gräns för det icke-linjära fallet. Detta åstadkoms genom att uppvisa konstant-snedvridning inbäddningar av snöflingade planmått i Euclidean utrymme. - Vad är det för fel på dig?
När det gäller linjära dimensionsminskningar visade REF en stark lägre gräns för p med p = 2.
Metric Structures in L1: Dimension, Snowflakes, and Average Distortion
{'venue': 'LATIN', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}