Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem

Assaf Naor, Terence Tao

Type: Article

Publication Date: 2012-03-28

Citations: 22

DOI: https://doi.org/10.1007/s11856-012-0039-7

View Publication

Download PDF

Locations

Israel Journal of Mathematics - View
arXiv (Cornell University) - View - PDF
Israel Journal of Mathematics - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem	2010	Assaf Naor Terence Tao
+ PDF	Lower Bounds for Oblivious Subspace Embeddings	2014	Jelani Nelson Huy L. Nguyễn
+ PDF Chat	Non-oblivious Strategy Improvement	2010	John Fearnley
+	Randomness-optimal oblivious sampling	1997	ZuckermanDavid
+ PDF Chat	Finding the Median (Obliviously) with Bounded Space	2015	Paul Beame Vincent Liew Mihai Pătraşcu
+	The asymptotic analysis of the structure-preserving doubling algorithms	2017	Yueh‐Cheng Kuo Wen-Wei Lin Shih-Feng Shieh
+	Compressibility and uniform complexity	1997	Montserrat Hermo
+	The disk-packing constant	1971	David W. Boyd
+	The disk-packing constant	1971	David W. Boyd
+ PDF Chat	The Forgiving Graph: a distributed data structure for low stretch under adversarial attack	2012	Thomas P. Hayes Jared Saia Amitabh Trehan
+ PDF	On the Analysis of Linear Probing Hashing	1998	Philippe Flajolet Patricio V. Poblete Alfredo Viola
+ PDF Chat	Linear Probing and Graphs	1998	Donald E. Knuth
+	The Compression Theorem of Rourke and Sanderson	2006	Daniel Mellis
+	The Blumenthal Conjecture	2013	W. Hayman T. Tyler D. White
+	Computation of Logarithmic Capacity	2010	Thomas Ransford
+	Hellinger volume and number-on-the-forehead communication complexity	2016	Troy Lee Nikos Leonardos Michael Saks Fengming Wang
+ PDF Chat	Sub-logarithmic Distributed Oblivious RAM with Small Block Size	2019	Eyal Kushilevitz Tamer Mour
+	oblation, n.	2023
+ PDF	Data-Dependent Generalization Bounds via Variable-Size Compressibility	2024	Milad Sefidgaran Abdellatif Zaidi
+ PDF	Data-dependent Generalization Bounds via Variable-Size Compressibility	2024	Milad Sefidgaran Abdellatif Zaidi

Works That Cite This (19)

Action	Title	Year	Authors
+ PDF	Covering metric spaces by few trees	2022	Yair Bartal Ora Nova Fandina Ofer Neiman
+ PDF	Two infinite versions of the nonlinear Dvoretzky theorem	2012	Kei Funano
+ PDF Chat	An introduction to the Ribe program	2012	Assaf Naor
+ PDF Chat	Ultrametric subsets with large Hausdorff dimension	2012	Manor Mendel Assaf Naor
+ PDF	Ramsey Spanning Trees and Their Applications	2020	Ittai Abraham Shiri Chechik Michael Elkin Arnold Filtser Ofer Neiman
+ PDF	Extension, Separation and Isomorphic Reverse Isoperimetry	2024	Assaf Naor
+	Ramsey Spanning Trees and their Applications	2017	Ittai Abraham Shiri Chechik Michael Elkin Arnold Filtser Ofer Neiman
+	Approximate Distance Oracle with Constant Query Time	2013	Shiri Chechik
+	Tree embeddings for hop-constrained network design	2021	Bernhard Haeupler D Ellis Hershkowitz Goran Žužić
+ PDF Chat	Hop-Constrained Metric Embeddings and their Applications	2022	Arnold Filtser

Works Cited by This (8)

Action	Title	Year	Authors
+	On hilbertian subsets of finite metric spaces	1986	Jean Bourgain T. Figiel Vitali Milman
+	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
+	An Isomorphic Version of Dvoretzky's Theorem, II	1998	Vitali Milman Gideon Schechtman
+ PDF	On metric Ramsey-type phenomena	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