Search

It is proved that for any $0<\beta<\alpha$, any bounded Ahlfors $\alpha$-regular space contains a $\beta$-regular compact subset that embeds biLipschitzly in an ultrametric with distortion at most $O(\alpha/(\alpha-\beta))$. The bound on the distortion is asymptotically tight when $\beta\to \alpha$. The main tool used in the proof is a regular form of the ultrametric skeleton theorem., Comment: 20 pages. Minor editing. Accepted to Studia Mathematica

The ultrametric skeleton theorem [Mendel, Naor 2013] implies, among other things, the following nonlinear Dvoretzky-type theorem for Hausdorff dimension: For any $0<\beta<\alpha$, any compact metric space $X$ of Hausdorff dimension $\alpha$ contains a subset which is biLipschitz equivalent to an ultrametric and has Hausdorff dimension at least $\beta$. In this note we present a simple proof of the ultrametric skeleton theorem in doubling spaces using Bartal's Ramsey decompositions [Bartal 2021]. The same general approach is also used to answer a question of Zindulka [Zindulka 2020] about the existence of "nearly ultrametric" subsets of compact spaces having full Hausdorff dimension., Comment: 13 pages, 1 figure. Minor changes and improvements. Accepted to "Analysis and Geometry in Metric Spaces"

A spanner is reliable if it can withstand large, catastrophic failures in the network. More precisely, any failure of some nodes can only cause a small damage in the remaining graph in terms of the dilation, that is, the spanner property is maintained for almost all nodes in the residual graph. Constructions of reliable spanners of near linear size are known in the low-dimensional Euclidean settings. Here, we present new constructions of reliable spanners for planar graphs, trees and (general) metric spaces., Comment: 29 pages, Full version after review

We prove that not every metric space embeds coarsely into an Alexandrov space of nonpositive curvature. This answers a question of Gromov (1993) and is in contrast to the fact that any metric space embeds coarsely into an Alexandrov space of nonnegative curvature, as shown by Andoni, Naor and Neiman (2015). We establish this statement by proving that a metric space which is $q$-barycentric for some $q\in [1,\infty)$ has metric cotype $q$ with sharp scaling parameter. Our proof utilizes nonlinear (metric space-valued) martingale inequalities and yields sharp bounds even for some classical Banach spaces. This allows us to evaluate the bi-Lipschitz distortion of the $\ell_\infty$ grid $[m]_\infty^n=(\{1,\ldots,m\}^n,\|\cdot\|_\infty)$ into $\ell_q$ for all $q\in (2,\infty)$, from which we deduce the following discrete converse to the fact that $\ell_\infty^n$ embeds with distortion $O(1)$ into $\ell_q$ for $q=O(\log n)$. A rigidity theorem of Ribe (1976) implies that for every $n\in \mathbb{N}$ there exists $m\in \mathbb{N}$ such that if $[m]_\infty^n$ embeds into $\ell_q$ with distortion $O(1)$, then $q$ is necessarily at least a universal constant multiple of $\log n$. Ribe's theorem does not give an explicit upper bound on this $m$, but by the work of Bourgain (1987) it suffices to take $m=n$, and this was the previously best-known estimate for $m$. We show that the above discretization statement actually holds when $m$ is a universal constant., Comment: Referees' comments addressed

Johnson and Lindenstrauss proved that any Lipschitz mapping from an $n$-point subset of a metric space into Hilbert space can be extended to the whole space, while increasing the Lipschitz constant by a factor of $O(\sqrt{\log n})$. We present a simplification of their argument that avoids dimension reduction and the Kirszbraun theorem., Comment: 3 pages. Incorporation of reviewers' suggestions

This short note contains an elementary observation in response to the recent posting arXiv:1707.06593v1, which studies the Lipschitz extension modulus to $n$ additional points. We bound this modulus in terms of the well-studied Lipschitz extension modulus from $n$ points to the entire ambient metric space, thus making it possible to quote the available literature to improve some of the bounds obtained in arXiv:1707.06593v1., Comment: not intended for publication

It is shown that there exists a sequence of 3-regular graphs $\{G_n\}_{n=1}^\infty$ and a Hadamard space $X$ such that $\{G_n\}_{n=1}^\infty$ forms an expander sequence with respect to $X$, yet random regular graphs are not expanders with respect to $X$. This answers a question of \cite{NS11}. $\{G_n\}_{n=1}^\infty$ are also shown to be expanders with respect to random regular graphs, yielding a deterministic sublinear time constant factor approximation algorithm for computing the average squared distance in subsets of a random graph. The proof uses the Euclidean cone over a random graph, an auxiliary continuous geometric object that allows for the implementation of martingale methods., Comment: incorporated Referees' comments

An ultrametric defined on a subset S of a metric space X can be extended to X while roughly preserving distances between pairs in S x X., Comment: 2 pages

The classical Okamura-Seymour theorem states that for an edge-capacitated, multi-commodity flow instance in which all terminals lie on a single face of a planar graph, there exists a feasible concurrent flow if and only if the cut conditions are satisfied. Simple examples show that a similar theorem is impossible in the node-capacitated setting. Nevertheless, we prove that an approximate flow/cut theorem does hold: For some universal c > 0, if the node cut conditions are satisfied, then one can simultaneously route a c-fraction of all the demands. This answers an open question of Chekuri and Kawarabayashi. More generally, we show that this holds in the setting of multi-commodity polymatroid networks introduced by Chekuri, et. al. Our approach employs a new type of random metric embedding in order to round the convex programs corresponding to these more general flow problems., Comment: 30 pages, 5 figures

Nonlinear spectral gaps with respect to uniformly convex normed spaces are shown to satisfy a spectral calculus inequality that establishes their decay along Cesaro averages. Nonlinear spectral gaps of graphs are also shown to behave sub-multiplicatively under zigzag products. These results yield a combinatorial construction of super-expanders, i.e., a sequence of 3-regular graphs that does not admit a coarse embedding into any uniformly convex normed space., Comment: Typos fixed based on referee comments. Some of the results of this paper were announced in arXiv:0910.2041. The corresponding parts of arXiv:0910.2041 are subsumed by the current paper

For every e>0, any subset of R^n with Hausdorff dimension larger than (1-e)n must have ultrametric distortion larger than 1/(4e)., Comment: 4 pages, improved layout

We prove that for every $\epsilon\in (0,1)$ there exists $C_\epsilon\in (0,\infty)$ with the following property. If $(X,d)$ is a compact metric space and $\mu$ is a Borel probability measure on $X$ then there exists a compact subset $S\subseteq X$ that embeds into an ultrametric space with distortion $O(1/\epsilon)$, and a probability measure $\nu$ supported on $S$ satisfying $\nu(B_d(x,r))\le (\mu(B_d(x,C_\epsilon r))^{1-\epsilon}$ for all $x\in X$ and $r\in (0,\infty)$. The dependence of the distortion on $\epsilon$ is sharp. We discuss an extension of this statement to multiple measures, as well as how it implies Talagrand's majorizing measures theorem., Comment: typos fixed

It is shown that for every $\e\in (0,1)$, every compact metric space $(X,d)$ has a compact subset $S\subseteq X$ that embeds into an ultrametric space with distortion $O(1/\e)$, and $$\dim_H(S)\ge (1-\e)\dim_H(X),$$ where $\dim_H(\cdot)$ denotes Hausdorff dimension. The above $O(1/\e)$ distortion estimate is shown to be sharp via a construction based on sequences of expander graphs., Comment: the order of the lemmas has been changed, added figures

We show that for every nondecreasing concave function w:R+ --> R+ with w(0)=0, either every finite metric space embeds with distortion arbitrarily close to 1 into a metric space of the form (X,w o d) for some metric d on X, or there exists a=a(w)>0 and n_0=n_0(w)\in N such that for all n>n_0, any embedding of {0,...,n} into a metric space of the form (X,w o d) incurs distortion at least n^a., Comment: 7 pages

It is shown that if (X, ||.||_X) is a Banach space with Rademacher cotype q then for every integer n there exists an even integer m< n^{1+1/q}$ such that for every f:Z_m^n --> X we have $\sum_{j=1}^n \Avg_x [ ||f(x+ (m/2) e_j)-f(x) ||_X^q ] < C m^q \Avg_{\e,x} [ ||f(x+\e)-f(x) ||_X^q ]$, where the expectations are with respect to uniformly chosen x\in Z_m^n and \e\in \{-1,0,1\}^n, and all the implied constants may depend only on q and the Rademacher cotype q constant of X. This improves the bound of m< n^{2+\frac{1}{q}} from [Mendel, Naor 2008]. The proof of the above inequality is based on a "smoothing and approximation" procedure which simplifies the proof of the metric characterization of Rademacher cotype of [Mendel, Naor 2008]. We also show that any such "smoothing and approximation" approach to metric cotype inequalities must require m> n^{(1/2)+(1/q)}., Comment: 27 pages, 1 figure. Fixes a slight error in the proof of Lemma 4.3 in the arXiv v2 and the published paper

Given a finite regular graph G=(V,E) and a metric space (X,d_X), let $gamma_+(G,X) denote the smallest constant $\gamma_+>0$ such that for all f,g:V\to X we have: \frac{1}{|V|^2}\sum_{x,y\in V} d_X(f(x),g(y))^2\le \frac{\gamma_+}{|E|} \sum_{xy\in E} d_X(f(x),g(y))^2. In the special case X=R this quantity coincides with the reciprocal of the absolute spectral gap of $G$, but for other geometries the parameter \gamma_+(G,X), which we still think of as measuring the non-linear spectral gap of G with respect to X (even though there is no actual spectrum present here), can behave very differently. Non-linear spectral gaps arise often in the theory of metric embeddings, and in the present paper we systematically study the theory of non-linear spectral gaps, partially in order to obtain a combinatorial construction of super-expander -- a family of bounded-degree graphs G_i=(V_i,E_i), with \lim_{i\to \infty} |V_i|=\infty, which do not admit a coarse embedding into any uniformly convex normed space. In addition, the bi-Lipschitz distortion of G_i in any uniformly convex Banach space is \Omega(\log |V_i|), which is the worst possible behavior due to Bourgain's embedding theorem. Such remarkable graph families were previously known to exist due to a tour de force algebraic construction of Lafforgue. Our construction is different and combinatorial, relying on the zigzag product of Reingold-Vadhan-Wigderson., Comment: 32 pages. Extended abstract. To be published (in abridged form) in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms 2010 (SODA '10)

We present fast algorithms for constructing probabilistic embeddings and approximate distance oracles in sparse graphs. The main ingredient is a fast algorithm for sampling the probabilistic partitions of Calinescu, Karloff, and Rabani in sparse graphs., Comment: 15 pages, title changed, a small error in the running time was fixed. Many errors in English were eliminated

It is shown that a Banach space admits an equivalent norm whose modulus of uniform convexity has power-type p if and only if it is Markov p-convex. Counterexamples are constructed to natural questions related to isomorphic uniform convexity of metric spaces, showing in particular that tree metrics fail to have the dichotomy property., Comment: 47 pages, full version, replacing the previous version which was an announcement

These are notes from talks given at ICMS, Edinburgh, 4/2007 ("Geometry and Algorithms workshop") and at Bernoulli Center, Lausanne 5/2007 ("Limits of graphs in group theory and computer science"). We survey the following type of dichotomies exhibited by certain classes X of finite metric spaces: For every host space H, either all metrics in X embed almost isometrically in H, or the distortion of embedding some metrics of X in H is unbounded., Comment: Lecture notes. 14 pages, 5 figures. Final version with only minor changes from the previous version

Let (X,d_X) be an n-point metric space. We show that there exists a distribution D over non-contractive embeddings into trees f:X-->T such that for every x in X, the expectation with respect to D of the maximum over y in X of the ratio d_T(f(x),f(y)) / d_X(x,y) is at most C (log n)^2, where C is a universal constant. Conversely we show that the above quadratic dependence on log n cannot be improved in general. Such embeddings, which we call maximum gradient embeddings, yield a framework for the design of approximation algorithms for a wide range of clustering problems with monotone costs, including fault-tolerant versions of k-median and facility location., Comment: 25 pages, 2 figures. Final version, minor revision of the previous one. To appear in "Combinatorica"

The competitive analysis fails to model locality of reference in the online paging problem. To deal with it, Borodin et. al. introduced the access graph model, which attempts to capture the locality of reference. However, the access graph model has a number of troubling aspects. The access graph has to be known in advance to the paging algorithm and the memory required to represent the access graph itself may be very large. In this paper we present truly online strongly competitive paging algorithms in the access graph model that do not have any prior information on the access sequence. We present both deterministic and randomized algorithms. The algorithms need only O(k log n) bits of memory, where k is the number of page slots available and n is the size of the virtual address space. I.e., asymptotically no more memory than needed to store the virtual address translation table. We also observe that our algorithms adapt themselves to temporal changes in the locality of reference. We model temporal changes in the locality of reference by extending the access graph model to the so called extended access graph model, in which many vertices of the graph can correspond to the same virtual page. We define a measure for the rate of change in the locality of reference in G denoted by Delta(G). We then show our algorithms remain strongly competitive as long as Delta(G) >= (1+ epsilon)k, and no truly online algorithm can be strongly competitive on a class of extended access graphs that includes all graphs G with Delta(G) >= k- o(k)., Comment: 37 pages. Preliminary version appeared in FOCS '97

This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (a.k.a. the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman). We then proceed to construct optimal Ramsey partitions, and use them to show that for every e\in (0,1), any n-point metric space has a subset of size n^{1-e} which embeds into Hilbert space with distortion O(1/e). This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor, in addition to considerably simplifying its proof. We use our new Ramsey partitions to design the best known approximate distance oracles when the distortion is large, closing a gap left open by Thorup and Zwick. Namely, we show that for any $n$ point metric space X, and k>1, there exists an O(k)-approximate distance oracle whose storage requirement is O(n^{1+1/k}), and whose query time is a universal constant. We also discuss applications of Ramsey partitions to various other geometric data structure problems, such as the design of efficient data structures for approximate ranking., Comment: 21 pages. Two explanatory figures were added, a few typos were fixed

We introduce the notion of scaled Enflo type of a metric space, and show that for Banach spaces, scaled Enflo type p is equivalent to Rademacher type p., Comment: 5 pages

We introduce the notion of cotype of a metric space, and prove that for Banach spaces it coincides with the classical notion of Rademacher cotype. This yields a concrete version of Ribe's theorem, settling a long standing open problem in the nonlinear theory of Banach spaces. We apply our results to several problems in metric geometry. Namely, we use metric cotype in the study of uniform and coarse embeddings, settling in particular the problem of classifying when L_p coarsely or uniformly embeds into L_q. We also prove a nonlinear analog of the Maurey-Pisier theorem, and use it to answer a question posed by Arora, Lovasz, Newman, Rabani, Rabinovich and Vempala, and to obtain quantitative bounds in a metric Ramsey theorem due to Matousek., Comment: 46 pages. Fixes the layout

We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure. This provides a refined and unified framework for the two primary methods of constructing Frechet embeddings for finite metrics, due to [Bourgain, 1985] and [Rao, 1999]. We prove that any n-point metric space (X,d) embeds in Hilbert space with distortion O(sqrt{alpha_X log n}), where alpha_X is a geometric estimate on the decomposability of X. As an immediate corollary, we obtain an O(sqrt{(log lambda_X) \log n}) distortion embedding, where \lambda_X is the doubling constant of X. Since \lambda_X\le n, this result recovers Bourgain's theorem, but when the metric X is, in a sense, ``low-dimensional,'' improved bounds are achieved. Our embeddings are volume-respecting for subsets of arbitrary size. One consequence is the existence of (k, O(log n)) volume-respecting embeddings for all 1 \leq k \leq n, which is the best possible, and answers positively a question posed by U. Feige. Our techniques are also used to answer positively a question of Y. Rabinovich, showing that any weighted n-point planar graph embeds in l_\infty^{O(log n)} with O(1) distortion. The O(log n) bound on the dimension is optimal, and improves upon the previously known bound of O((log n)^2)., Comment: 17 pages. No figures. Appeared in FOCS '04. To appeaer in Geometric & Functional Analysis. This version fixes a subtle error in Section 2.2

We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: Approximate nearest neighbor search, well-separated pair decomposition, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near-linear and the space being used is linear., Comment: 41 pages. Extensive clean-up of minor English errors

Metric embedding has become a common technique in the design of algorithms. Its applicability is often dependent on how high the embedding's distortion is. For example, embedding finite metric space into trees may require linear distortion as a function of its size. Using probabilistic metric embeddings, the bound on the distortion reduces to logarithmic in the size. We make a step in the direction of bypassing the lower bound on the distortion in terms of the size of the metric. We define "multi-embeddings" of metric spaces in which a point is mapped onto a set of points, while keeping the target metric of polynomial size and preserving the distortion of paths. The distortion obtained with such multi-embeddings into ultrametrics is at most O(log Delta loglog Delta) where Delta is the aspect ratio of the metric. In particular, for expander graphs, we are able to obtain constant distortion embeddings into trees in contrast with the Omega(log n) lower bound for all previous notions of embeddings. We demonstrate the algorithmic application of the new embeddings for two optimization problems: group Steiner tree and metrical task systems.

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 algorithms. Additionally, many open questions in geometric non-linear functional analysis involve the properties of finite subsets of L_1., Comment: 9 pages, 1 figure. To appear in European Journal of Combinatorics. Preliminary version appeared in LATIN '04

Frechet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Frechet embedding is Bourgain's embedding. The authors have recently shown that for every e>0 any n-point metric space contains a subset of size at least n^(1-e) which embeds into l_2 with distortion O(\log(2/e) /e). The embedding we used is non-Frechet, and the purpose of this note is to show that this is not coincidental. Specifically, for every e>0, we construct arbitrarily large n-point metric spaces, such that the distortion of any Frechet embedding into l_p on subsets of size at least n^{1/2 + e} is \Omega((\log n)^{1/p})., Comment: 10 pages, 1 figure

The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of finite metric spaces. Namely, we prove statements of the form "Every finite metric space contains a large subspace that is nearly quilateral or far from being equilateral". We consider two distinct interpretations for being "far from equilateral". Proximity among metric spaces is quantified through the metric distortion D. We provide tight asymptotic answers for these problems. In particular, we show that a phase transition occurs at D=2., Comment: 14 pages, 0 figures

This paper is concerned with online caching algorithms for the (n,k)-companion cache, defined by Brehob et. al. In this model the cache is composed of two components: a k-way set-associative cache and a companion fully-associative cache of size n. We show that the deterministic competitive ratio for this problem is (n+1)(k+1)-1, and the randomized competitive ratio is O(\log n \log k) and \Omega(\log n +\log k)., Comment: 17 pages, 1 figure. Preliminary version in ESA '02. To be published in Theoretical Computer Science A

This paper is devoted to the study of quotients of finite metric spaces. The basic type of question we ask is: Given a finite metric space M, what is the largest quotient of (a subset of) M which well embeds into Hilbert space. We obtain asymptotically tight bounds for these questions, and prove that they exhibit phase transitions. We also study the analogous problem for embedings into l_p, and the particular case of the hypercube., Comment: 36 pages, 0 figures. To appear in Advances in Mathematics

Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain improved randomized online algorithms for metrical task systems on arbitrary metric spaces., Comment: 20 pages, 1 figure

The paper referred to in the title is withdrawn., Comment: The paper is withdrawn

The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky's theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric space on n points, we seek its subspace of largest cardinality which can be embedded with a given distortion in Hilbert space. We provide nearly tight upper and lower bounds on the cardinality of this subspace in terms of n and the desired distortion. Our main theorem states that for any epsilon>0, every n point metric space contains a subset of size at least n^{1-\epsilon} which is embeddable in Hilbert space with O(\frac{\log(1/\epsilon)}{\epsilon}) distortion. The bound on the distortion is tight up to the log(1/\epsilon) factor. We further include a comprehensive study of various other aspects of this problem., Comment: 67 pages, published version

A nearly logarithmic lower bound on the randomized competitive ratio for the metrical task systems problem is presented. This implies a similar lower bound for the extensively studied k-server problem. The proof is based on Ramsey-type theorems for metric spaces, that state that every metric space contains a large subspace which is approximately a hierarchically well-separated tree (and in particular an ultrametric). These Ramsey-type theorems may be of independent interest., Comment: Fix an error in the metadata. 31 pages, 0 figures. Preliminary version in FOCS '01. To be published in J. Comput. System Sci