Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem

Assaf Naor, Terence Tao

Type: Preprint

Publication Date: 2010-01-01

Citations: 3

DOI: https://doi.org/10.48550/arxiv.1003.4013

View Publication

Locations

arXiv (Cornell University) - View
arXiv (Cornell University) - View - PDF
DataCite API - View
arXiv (Cornell University) - View
arXiv (Cornell University) - View - PDF
DataCite API - View
arXiv (Cornell University) - View
arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem	2012	Assaf Naor Terence Tao
+	Inapproximability for metric embeddings into R^d	2008	Jiřı́ Matoušek Anastasios Sidiropoulos
+	Online embedding of metrics	2023	Ilan Newman Yuri Rabinovich
+	Almost Optimal Explicit Johnson-Lindenstrauss Transformations	2010	Raghu Meka
+	Almost Optimal Explicit Johnson-Lindenstrauss Transformations	2010	Raghu Meka
+	Binary Embedding: Fundamental Limits and Fast Algorithm	2015	Xinyang Yi Constantine Caramanis Eric Price
+	Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets	2015	Samet Oymak Ben Recht
+	Binary Embedding: Fundamental Limits and Fast Algorithm	2015	Xinyang Yi Constantine Caramanis Eric Price
+	Metric Dichotomies	2007	Manor Mendel
+	Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings	2023	Sujoy Bhore Arnold Filtser Csaba D. Tóth
+	The Randomized Dvoretzky’s Theorem in $$l_{\infty }^{n}$$ and the χ-Distribution	2014	Konstantin Tikhomirov
+ PDF Chat	Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings	2024	Sujoy Bhore Arnold Filtser Csaba D. Tóth
+ PDF	On metric Ramsey-type phenomena	2005	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+ PDF Chat	On metric ramsey-type phenomena	2003	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+ PDF Chat	On metric ramsey-type phenomena	2003	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+	Metric Dichotomies	2007	Manor Mendel
+	Metric embedding with outliers	2015	Anastasios Sidiropoulos Yusu Wang
+	Barriers for Faster Dimensionality Reduction	2022	Ora Nova Fandina Mikael Møller Høgsgaard Kasper Green Larsen
+	Lower Bounds on the Low-Distortion Embedding Dimension of Submanifolds of $\mathbb{R}^n$	2021	Mark Iwen Arman Tavakoli B. Schmidt
+	On constant factor approximation for earth mover distance over doubling metrics	2010	Shi Li

Works That Cite This (4)

Action	Title	Year	Authors
+	Two infinite versions of nonlinear Dvoretzky's theorem	2011	Kei Funano
+	Embedding proper ultrametric spaces into $\ell_p$ and its application to nonlinear Dvoretzky's theorem	2012	Kei Funano
+ PDF Chat	Ultrametric subsets with large Hausdorff dimension	2012	Manor Mendel Assaf Naor
+ PDF Chat	Approximate Distance Oracles with Improved Query Time	2013	Christian Wulff‐Nilsen

Works Cited by This (7)

Action	Title	Year	Authors
+	A tight threshold for metric Ramsey phenomena	2005	Moses Charikar Adriana Karagiozova
+ PDF	Some Low Distortion Metric Ramsey Problems	2004	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+ PDF	Ramsey partitions and proximity data structures	2007	Manor Mendel Assaf Naor
+	Two observations regarding embedding subsets of Euclidean spaces in normed spaces	2004	Gideon Schechtman
+ PDF	On metric Ramsey-type phenomena	2005	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+	ON METRIC RAMSEY-TYPE DICHOTOMIES	2005	Yair Bartal Nathan Linial Manor Mendel Assaf Naor
+	Ramsey-type theorems for metric spaces with applications to online problems	2006	Yair Bartal Béla Bollobás Manor Mendel