We design a deterministic algorithm that, given \(n\) points in a typical constant degree regular graph, queries \(O(n)\) distances to output a constant factor approximation to the average distance among those points, thus answering a question posed in [Mendel and Naor 2015]. Our algorithm uses the method of [Mendel and Naor 2015] to construct a sequence of constant degree graphs that are expanders with respect to certain nonpositively curved metric spaces, together with a new rigidity theorem for metric transforms of nonpositively curved metric spaces. The fact that our algorithm works for typical (uniformly random) constant degree regular graphs rather than for all constant degree graphs is unavoidable, thanks to the following impossibility result that we obtain: For every fixed \(k \in \mathbb N\), the approximation factor of any algorithm for average distance that works for all constant degree graphs and queries \(o(n^{1+1/k})\) distances must necessarily be at least \(2(k + 1)\). This matches the upper bound attained by the algorithm that was designed for general finite metric spaces in [Barhum et. al. 2007]. Thus, any algorithm for average distance in constant degree graphs whose approximation guarantee is less than 4 must query \(\Omega(n^2)\) distances, any such algorithm whose approximation guarantee is less than 6 must query \(\Omega(n^{3/2})\) distances, any such algorithm whose approximation guarantee less than 8 must query \(\Omega(n^{3/4})\) distances, and so forth, and furthermore there exist algorithms achieving those parameters.

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. In other words, 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.

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.

It is shown that there exists a sequence of 3-regular graphs {Gn}∞n=1 and a Hadamard space X such that {Gn}∞n=1 forms an expander sequence with respect to {X{, yet random regular graphs are not expanders with respect to {X{. This answers a question of [31]. {Gn}∞n=1 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.

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 ε > 0, if the node cut conditions are satisfied, then one can simultaneously route an ε-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.

Given a finite regular graph G = (V, E) and a metric space (X, dX), let γ+(G, X) denote the smallest constant γ+ > 0 such that for all f, g: V → X we have: In the special case X = ℝ this quantity coincides with the reciprocal of the absolute spectral gap of G, but for other geometries the parameter γ+(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 Gi = (Vi, Ei), with limi→∞ |Vi| = ∞, which do not admit a coarse embedding into any uniformly convex normed space. In addition, the bi-Lipschitz distortion of Gi in any uniformly convex Banach space is Ω(log |Vi|), which is the worst possible behavior due to Bourgain's embedding theorem [3]. Such remarkable graph families were previously known to exist due to a tour de force algebraic construction of Lafforgue [11]. Our construction is different and combinatorial, relying on the zigzag product of Reingold-Vadhan-Wigderson [28]. We show that non-linear spectral gaps behave sub-multiplicatively under zigzag products — a fact that amounts to a simple iteration of the inequality above. This yields as a special case a very simple (linear algebra free) proof of the Reingold-Vadhan-Wigderson theorem which states that zigzag products preserve the property of having an absolute spectral gap (with quantitative control on the size of the gap). The zigzag iteration of Reingold-Vadhan-Wigderson also involves taking graph powers, which is trivial to analyze in the classical “linear” setting. In our work, the behavior of non-linear spectral gaps under graph powers becomes a major geometric obstacle, and we show that for uniformly convex normed spaces there exists a satisfactory substitute for spectral calculus which makes sense in the non-linear setting. These facts, in conjunction with a variant of Ball's notion of Markov cotype and a Fourier analytic proof of the existence of appropriate “base graphs”, are shown to imply that Reingold-Vadhan-Wigderson type constructions can be carried out in the non-linear setting.

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.

This paper addresses the non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce and construct optimal Ramsey partitions, and use them to show that for every epsiv isin (0,1), any n-point metric space has a subset of size n1-epsivwhich embeds into Hilbert space with distortion O(1/epsiv). This result is best possible and improves part of the metric Ramsey theorem of Bartal et al. (2005), in addition to considerably simplifying its proof. We use our new Ramsey partitions to design approximate distance oracles with a universal constant query time, closing a gap left open by Thorup and Zwick (2005). Namely, we show that for any n point metric space X, and k ges 1, there exists an O(k)-approximate distance oracle whose storage requirement is O(n1+1k/), and whose query time is a universal constant. We also discuss applications to various other geometric data structures, and the relation to well separated pair decompositions

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, spanner construction, 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.

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, spanner construction, 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.

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 J. Bourgain and S. Rao. We prove that any n-point metric space (X, d) embeds in Hilbert space with distortion O(/spl radic//spl alpha//sub X//spl middot/log n), where /spl alpha//sub X/ is a geometric estimate on the decomposability of X. An an immediate corollary, we obtain an O(/spl radic/log /spl lambda//sub X//spl middot/log n) distortion embedding, where /spl lambda//sub X/ is the doubling constant of X. Since /spl lambda//sub X/ /spl les/ n, this result recovers Bourgain 5 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 /spl les/ k /spl les/ 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 /spl lscr//sub /spl infin///sup 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/sup 2/ n).

Metric embedding has become a common technique in the design of algorithms. Its applicability is often dependent on how large the embedding's distortion is. For example, embedding finite metric space into trees may require linear distortion as a function of the size of the metric. Using probabilistic metric embeddings, the bound on the distortion reduces to logarithmic in the size of the metric. 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 "multiembeddings" 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 multiembeddings into ultrametrics is at most $O(\log \Delta\log\log \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.

This paper deals with Ramsey-type theorems for metric spaces. Such a theorem states that every n point metric space contains a large subspace which can be embedded with some fixed distortion in a metric space from some special class.Our main theorem states that for any ε>0, every n point metric space contains a subspace of size at least n1-ε which is embeddable in an ultrametric with O(log(1/ε)/ε distortion. This in particular provides a bound for embedding in Euclidean spaces. The bound on the distortion is tight up to the log(1/ε) factor even for embedding in arbitrary Euclidean spaces. This result can be viewed as a non-linear analog of Dvoretzky's theorem, a cornerstone of modern Banach space theory and convex geometry.Our main Ramsey-type theorem and techniques naturally extend to give theorems for classes of hierarchically well-separated trees which have algorithmic implications, and can be viewed as the solution of a natural clustering problem.We further include a comprehensive study of various other aspects of the metric Ramsey problem.

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.

The paper gives a nearly logarithmic lower bound on the randomized competitive ratio for a Metrical Task Systems model (A. Borodin et al., 1992). This implies a similar lower bound for the extensively studied K-server problem. Our proof is based on proving a Ramsey-type theorem for metric spaces. In particular, we prove that in every metric space there exists a large subspace which is approximately a "hierarchically well-separated tree" (HST) (Y. Bartal, 1996). This theorem may be of independent interest.

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 the following results:1. Better randomized algorithms for unfair metrical task systems on the uniform metric space.2. Better randomized algorithms for metrical task systems on general metric spaces, O(log z n(log log n) 2) competitive, improving on the best previous result of O(log s n log log n).3. A tight randomized competitive ratio for the k-weighted caching problem on k+l points, O(log k), improving on the best previous result of O(log 2 k).

The access graph model for paging, defined by (Borodin et al., 1991) and studied in (Irani et al., 1992) 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. We present a truly online strongly competitive paging algorithm in the access graph model that does not have any prior information on the access sequence. We give both strongly competitive deterministic and strongly competitive randomized algorithms. Our 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., no more memory than needed to store the virtual translation tables for pages in memory. In fact, we can reduce this to O(k log k) bits using appropriate probabilistic data structures. We also extend the locality of reference concept captured by the access graph model to allow changes in the behavior of the underlying process. We formalize this by introducing the concept of an "extended access graph". We consider a graph parameter /spl Delta/ that captures the degree of change allowed. We study this new model and give algorithms that are strongly competitive for the (unknown) extended access graph. We can do so for almost all values of /spl Delta/ for which it is possible.