Ofer Neiman

TCS Journal 2022 Journal Article

Distributed strong diameter network decomposition

• Michael Elkin
• Ofer Neiman

For a pair of positive parameters D, χ, a partition P of the vertex set V of an n-vertex graph G = ( V, E ) into disjoint clusters of diameter at most D each is called a ( D, χ ) network decomposition, if the supergraph G ( P ), obtained by contracting each of the clusters of P, can be properly χ-colored. The decomposition P is said to be strong (resp. , weak) if each of the clusters has strong (resp. , weak) diameter at most D, i. e. , if for every cluster C ∈ P and every two vertices u, v ∈ C, the distance between them in the induced graph G ( C ) of C (resp. , in G) is at most D. Network decomposition is a powerful construct, very useful in distributed computing and beyond. In this paper we show that strong ( O ( log ⁡ n ), O ( log ⁡ n ) ) network decompositions can be computed in O ( log 2 ⁡ n ) time in the CONGEST model. We also present a tradeoff between parameters of our network decomposition. Our work is inspired by and relies on the “shifted shortest path approach”, due to Blelloch et al. [11], and Miller et al. [20]. These authors developed this approach for PRAM algorithms for padded partitions. We adapt their approach to network decompositions in the distributed model of computation.

SODA Conference 2020 Conference Paper

Lossless Prioritized Embeddings

• Michael Elkin
• Ofer Neiman

Given metric spaces ( X, d ) and ( Y, ρ ) and an ordering x 1, x 2, …, x n of ( X, d ), an embedding f: X → Y is said to have a prioritized distortion α (·), for a function α (·), if for any pair x j, x ′ of distinct points in X, the distortion provided by f for this pair is at most a ( j ). If Y is a normed space, the embedding is said to have prioritized dimension β (·), if f ( x j ) may have at most β ( j ) nonzero coordinates. The notion of prioritized embedding was introduced by Filtser and the current authors in [EFN18], where a rather general methodology for constructing such embeddings was developed. Though this methodology enabled [EFN18] to come up with many prioritized embeddings, it typically incurs some loss in the distortion. In other words, in the worst-case, prioritized embeddings obtained via this methodology incur distortion which is at least a constant factor off, compared to the distortion of the classical counterparts of these embeddings. This constant loss is problematic for isometric embeddings. It is also troublesome for Matousek's embedding of general metrics into ℓ ∞, which for a parameter k = 1, 2, …, provides distortion 2 k– 1 and dimension O ( k log n·n 1/ k ). In this paper we devise two lossless prioritized embeddings. The first one is an isometric prioritized embedding of tree metrics into with dimension O (log j ), matching the worst-case guarantee of O (log n ) of the classical embedding of Linial et al. [LLR95]. The second one is a prioritized Matousek's embedding of general metrics into ℓ ∞, which for a parameter k = 1, 2, …, provides prioritized distortion and dimension O ( k log n · n 1/ k ), again matching the worst-case guarantee 2 k – 1 in the distortion of the classical Matousek's embedding. We also provide a dimension-prioritized variant of Matousek's embedding. Finally, we devise prioritized embeddings of general metrics into (single) ultra-metric and of general graphs into (single) spanning tree with asymptotically optimal distortion.

NeurIPS Conference 2019 Conference Paper

Dimensionality reduction: theoretical perspective on practical measures

• Yair Bartal
• Nova Fandina
• Ofer Neiman

Dimensionality reduction plays a central role in real-world applications for Machine Learning, among many fields. In particular, metric dimensionality reduction where data from a general metric is mapped into low dimensional space, is often used as a first step before applying machine learning algorithms. In almost all these applications the quality of the embedding is measured by various average case criteria. Metric dimensionality reduction has also been studied in Math and TCS, within the extremely fruitful and influential field of metric embedding. Yet, the vast majority of theoretical research has been devoted to analyzing the worst case behavior of embeddings and therefore has little relevance to practical settings. The goal of this paper is to bridge the gap between theory and practice view-points of metric dimensionality reduction, laying the foundation for a theoretical study of more practically oriented analysis. This paper can be viewed as providing a comprehensive theoretical framework addressing a line of research initiated by VL [NeuroIPS' 18] who have set the goal of analyzing different distortion measurement criteria, with the lens of Machine Learning applicability, from both theoretical and practical perspectives. We complement their work by considering some important and vastly used average case criteria, some of which originated within the well-known Multi-Dimensional Scaling framework. While often studied in practice, no theoretical studies have thus far attempted at providing rigorous analysis of these criteria. In this paper we provide the first analysis of these, as well as the new distortion measure developed by [VL18] designed to possess Machine Learning desired properties. Moreover, we show that all measures considered can be adapted to possess similar qualities. The main consequences of our work are nearly tight bounds on the absolute values of all distortion criteria, as well as first approximation algorithms with provable guarantees.

STOC Conference 2018 Conference Paper

Metric embedding via shortest path decompositions

• Ittai Abraham
• Arnold Filtser
• Anupam Gupta 0001
• Ofer Neiman

We study the problem of embedding weighted graphs of pathwidth k into ℓ p spaces. Our main result is an O ( k min{1 p ,12} )-distortion embedding. For p =1, this is a super-exponential improvement over the best previous bound of Lee and Sidiropoulos. Our distortion bound is asymptotically tight for any fixed p >1.

SODA Conference 2018 Conference Paper

Ramsey Spanning Trees and their Applications

• Ittai Abraham
• Shiri Chechik
• Michael Elkin
• Arnold Filtser
• Ofer Neiman

The metric Ramsey problem asks for the largest subset S of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion. Study of this problem was motivated as a non-linear version of Dvoretzky theorem. Mendel and Naor [MN07] devised the so called Ramsey Partitions to address this problem, and showed the algorithmic applications of their techniques to approximate distance oracles and ranking problems. In this paper we study the natural extension of the metric Ramsey problem to graphs, and introduce the notion of Ramsey Spanning Trees. We ask for the largest subset S ⊆ V of a given graph G = ( V, E ), such that there exists a spanning tree of G that has small stretch for S. Applied iteratively, this provides a small collection of spanning trees, such that each vertex has a tree providing low stretch paths to all other vertices. The union of these trees serves as a special type of spanner, a tree-padding spanner. We use this spanner to devise the first compact stateless routing scheme with O (1) routing decision time, and labels which are much shorter than in all currently existing schemes. We first revisit the metric Ramsey problem, and provide a new deterministic construction. We prove that for every k, any n -point metric space has a subset S of size at least n 1–1/ k which embeds into an ultrametric with distortion 8 k. We use this result to obtain the state-of-the-art deterministic construction of a distance oracle. Building on this result, we prove that for every k, any n -vertex graph G = ( V, E ) has a subset S of size at least n 1–1/ k, and a spanning tree of G, that has stretch O ( k log log n ) between any point in S and any point in V.

SODA Conference 2017 Conference Paper

Efficient Algorithms for Constructing Very Sparse Spanners and Emulators

• Michael Elkin
• Ofer Neiman

Miller et al. [43] devised a distributed 1 algorithm in the CONGEST model, that given a parameter k = 1, 2, …, constructs an O ( k )-spanner of an input unweighted n -vertex graph with O ( n 1 + 1/ k ) expected edges in O ( k ) rounds of communication. In this paper we improve the result of [43], by showing a k -round distributed algorithm in the same model, that constructs a (2 k — 1)- spanner with O ( n 1+1/ k /∊) edges, with probability 1 — ∊, for any ∊ > 0. Moreover, when k = ω(log n ), our algorithm produces (still in k rounds) ultra-sparse spanners, i. e. , spanners of size n (1 + o (1)), with probability 1 — o (1). To our knowledge, this is the first distributed algorithm in the CONGEST or in the PRAM models that constructs spanners or skeletons (i. e. , connected spanning subgraphs) that sparse. Our algorithm can also be implemented in linear time in the standard centralized model, and for large k, it provides spanners that are sparser than any other spanner given by a known ( n ear-)linear time algorithm. We also devise improved bounds (and algorithms realizing these bounds) for (1 + ∊, ß)-spanners and emulators. In particular, we show that for any unweighted n -vertex graph and any ∊ > 0, there exists a with O ( n ) edges. All previous constructions of (1 + ∊, β )-spanners and emulators employ a superlinear number of edges, for all choices of parameters. Finally, we provide some applications of our results to approximate shortest paths’ computation in unweighted graphs.

TCS Journal 2017 Journal Article

Terminal embeddings

• Michael Elkin
• Arnold Filtser
• Ofer Neiman

In this paper we study terminal embeddings, in which one is given a finite metric ( X, d X ) (or a graph G = ( V, E ) ) and a subset K ⊆ X of its points are designated as terminals. The objective is to embed the metric into a normed space, while approximately preserving all distances among pairs that contain a terminal. We devise such embeddings in various settings, and conclude that even though we have to preserve ≈ | K | ⋅ | X | pairs, the distortion depends only on | K |, rather than on | X |. We also strengthen this notion, and consider embeddings that approximately preserve the distances between all pairs, but provide improved distortion for pairs containing a terminal. Surprisingly, we show that such embeddings exist in many settings, and have optimal distortion bounds both with respect to X × X and with respect to K × X. Moreover, our embeddings have implications to the areas of Approximation and Online Algorithms. In particular, [10] devised an O ˜ ( log ⁡ r ) -approximation algorithm for sparsest-cut instances with r demands. Building on their framework, we provide an O ˜ ( log ⁡ | K | ) - approximation for sparsest-cut instances in which each demand is incident on one of the vertices of K (aka, terminals). Since | K | ≤ r, our bound generalizes that of [10].

FOCS Conference 2016 Conference Paper

Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths

• Michael Elkin
• Ofer Neiman

A (β, ∈)-hopset for a weighted undirected n-vertex graph G = (V, E) is a set of edges, whose addition to the graph guarantees that every pair of vertices has a path between them that contains at most β edges, whose length is within 1 + ∈ of the shortest path. In her seminal paper, Cohen [8, JACM 2000] introduced the notion of hopsets in the context of parallel computation of approximate shortest paths, and since then it has found numerous applications in various other settings, such as dynamic graph algorithms, distributed computing, and the streaming model. Cohen [8] devised efficient algorithms for constructing hopsets with polylogarithmic in n number of hops. Her constructions remain the state-of-the-art since the publication of her paper in STOC'94, i. e. , for more than two decades. In this paper we exhibit the first construction of sparse hopsets with a constant number of hops. We also find efficient algorithms for hopsets in various computational settings, improving the best known constructions. Generally, our hopsets strictly outperform the hopsets of [8], both in terms of their parameters, and in terms of the resources required to construct them. We demonstrate the applicability of our results for the fundamental problem of computing approximate shortest paths from s sources. Our results improve the running time for this problem in the parallel, distributed and streaming models, for a vast range of s.

SODA Conference 2016 Conference Paper

On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion

• Yair Bartal
• Arnold Filtser
• Ofer Neiman

Minimum Spanning Trees of weighted graphs are fundamental objects in numerous applications. In particular in distributed networks, the minimum spanning tree of the network is often used to route messages between network nodes. Unfortunately, while being most efficient in the total cost of connecting all nodes, minimum spanning trees fail miserably in the desired property of approximately preserving distances between pairs. While known lower bounds exclude the possibility of the worst case distortion of a tree being small, it was shown in [4] that there exists a spanning tree with constant average distortion. Yet, the weight of such a tree may be significantly larger than that of the MST. In this paper, we show that any weighted undirected graph admits a spanning tree whose weight is at most (1 + ρ ) times that of the MST, providing constant average distortion O (1/ ρ 2 ). 1 The constant average distortion bound is implied by a stronger property of scaling distortion, i. e. , improved distortion for smaller fractions of the pairs. The result is achieved by first showing the existence of a low weight spanner with small prioritized distortion, a property allowing to prioritize the nodes whose associated distortions will be improved. We show that prioritized distortion is essentially equivalent to coarse scaling distortion via a general transformation, which has further implications and may be of independent interest. In particular, we obtain an embedding for arbitrary metrics into Euclidean space with optimal prioritized distortion.

TCS Journal 2016 Journal Article

Space-efficient path-reporting approximate distance oracles

• Michael Elkin
• Ofer Neiman
• Christian Wulff-Nilsen

We consider approximate path-reporting distance oracles, distance labeling and labeled routing with extremely low space requirements, for general undirected graphs. For distance oracles, we show how to break the n log ⁡ n space bound of Thorup and Zwick if approximate paths rather than distances need to be reported. For approximate distance labeling and labeled routing, we break the previously best known space bound of O ( log ⁡ n ) words per vertex. The cost for such space efficiency is an increased stretch.

STOC Conference 2015 Conference Paper

Prioritized Metric Structures and Embedding

• Michael Elkin
• Arnold Filtser
• Ofer Neiman

Metric data structures (distance oracles, distance labeling schemes, routing schemes) and low-distortion embeddings provide a powerful algorithmic methodology, which has been successfully applied for approximation algorithms [21], online algorithms [7], distributed algorithms [19] and for computing sparsifiers [28]. However, this methodology appears to have a limitation: the worst-case performance inherently depends on the cardinality of the metric, and one could not specify in advance which vertices/points should enjoy a better service (i.e., stretch/distortion, label size/dimension) than that given by the worst-case guarantee.

STOC Conference 2014 Conference Paper

Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs

• Ittai Abraham
• Cyril Gavoille
• Anupam Gupta 0001
• Ofer Neiman
• Kunal Talwar

We prove that any graph excluding K r as a minor has can be partitioned into clusters of diameter at most Δ while removing at most O ( r/ Δ) fraction of the edges. This improves over the results of Fakcharoenphol and Talwar, who building on the work of Klein, Plotkin and Rao gave a partitioning that required to remove O ( r 2 /Δ) fraction of the edges. Our result is obtained by a new approach that relates the topological properties (excluding a minor) of a graph to its geometric properties (the induced shortest path metric). Specifically, we show that techniques used by Andreae in his investigation of the cops and robbers game on graphs excluding a fixed minor, can be used to construct padded decompositions of the metrics induced by such graphs. In particular, we get probabilistic partitions with padding parameter O ( r ) and strong-diameter partitions with padding parameter O ( r 2 ) for K r -free graphs, O ( k ) for treewidth- k graphs, and O (log g ) for graphs with genus g .

TCS Journal 2013 Journal Article

Bandwidth and low dimensional embedding

• Yair Bartal
• Douglas E. Carroll
• Adam Meyerson
• Ofer Neiman

We design an algorithm to embed graph metrics into ℓ p with dimension and distortion both dependent only upon the bandwidth of the graph. In particular, we show that any graph of bandwidth k embeds with distortion polynomial in k into ℓ p O ( log k ), 1 ⩽ p ⩽ ∞. Prior to our result the only known embedding with distortion independent of n was into high dimensional ℓ 1 and had distortion exponential in k. Our low dimensional embedding is based on a general method for reducing the dimension of an ℓ p embedding. This method requires that the embedding satisfy certain conditions, and the dimension is reduced to the intrinsic dimension of the point set, without substantially increasing the distortion. We observe that the family of graphs with bounded bandwidth are doubling, thus our main result can be viewed as a positive answer to a conjecture of Assouad (1983) [2], limited to this family. We also study an extension to graphs of bounded tree-bandwidth.

STOC Conference 2013 Conference Paper

Simple deterministic algorithms for fully dynamic maximal matching

• Ofer Neiman
• Shay Solomon

FOCS Conference 2012 Conference Paper

Beck's Three Permutations Conjecture: A Counterexample and Some Consequences

• Alantha Newman
• Ofer Neiman
• Aleksandar Nikolov

Given three permutations on the integers 1 through n, consider the set system consisting of each interval in each of the three permutations. In 1982, Beck conjectured that the discrepancy of this set system is O(1). In other words, the conjecture says that each integer from 1 through n can be colored either red or blue so that the number of red and blue integers in each interval of each permutations differs only by a constant. (The discrepancy of a set system based on two permutations is at most two.) Our main result is a counterexample to this conjecture: for any positive integer n = 3 k, we construct three permutations whose corresponding set system has discrepancy Ω(log n). Our counterexample is based on a simple recursive construction, and our proof of the discrepancy lower bound is by induction. This construction also disproves a generalization of Beck's conjecture due to Spencer, Srinivasan and Tetali, who conjectured that a set √ system corresponding to £ permutations has discrepancy O(√ℓ). Our work was inspired by an intriguing paper from SODA 2011 by Eisenbrand, Palvolgyi and Rothvoß, who show a surprising connection between the discrepancy of three permutations and the bin packing problem: They show that Beck's conjecture implies a constant worst-case bound on the additive integrality gap for the Gilmore-Gomory LP relaxation for bin packing in the special case when all items have sizes strictly between 1/4 and 1/2, also known as the three partition problem. Our counterexample shows that this approach to bounding the additive integrality gap for bin packing will not work. We can, however, prove an interesting implication of our construction in the reverse direction: there are instances of bin packing and corresponding optimal basic feasible solutions for the Gilmore-Gomory LP relaxation such that any packing that contains only patterns from the support of these solutions requires at least opt + Ω(log m) bins, where m is the number of items. Finally, we discuss some implications that our construction has for other areas of discrepancy theory.

STOC Conference 2012 Conference Paper

Using petal-decompositions to build a low stretch spanning tree

• Ittai Abraham
• Ofer Neiman

We prove that any graph G=(V,E) with n points and m edges has a spanning tree T such that ∑ (u,v)∈ E(G) d T (u,v) = O(m log n log log n). Moreover such a tree can be found in time O(m log n log log n). Our result is obtained using a new petal-decomposition approach which guarantees that the radius of each cluster in the tree is at most 4 times the radius of the induced subgraph of the cluster in the original graph.

FOCS Conference 2011 Conference Paper

Near Linear Lower Bound for Dimension Reduction in L1

• Alexandr Andoni
• Moses Charikar
• Ofer Neiman
• Huy L. Nguyên

Given a set of n points in ℓ 1, how many dimensions are needed to represent all pair wise distances within a specific distortion? This dimension-distortion tradeoff question is well understood for the ℓ 2 norm, where O((log n)/ϵ 2 ) dimensions suffice to achieve 1+ϵ distortion. In sharp contrast, there is a significant gap between upper and lower bounds for dimension reduction in ℓ 1. A recent result shows that distortion 1+ϵ can be achieved with n/ϵ 2 dimensions. On the other hand, the only lower bounds known are that distortion δ requires n Ω(1/δ 2 ) dimensions and that distortion 1+ϵ requires n 1/2-O(ϵ log(1/ϵ)) dimensions. In this work, we show the first near linear lower bounds for dimension reduction in ℓ 1. In particular, we show that 1+ϵ distortion requires at least n 1-O(1 / log(1/ϵ)) dimensions. Our proofs are combinatorial, but inspired by linear programming. In fact, our techniques lead to a simple combinatorial argument that is equivalent to the LP based proof of Brinkman-Charikar for lower bounds on dimension reduction in ℓ 1.

SODA Conference 2009 Conference Paper

On low dimensional local embeddings

• Ittai Abraham
• Yair Bartal
• Ofer Neiman

We study the problem of embedding metric spaces into low dimensional ℓ p spaces while faithfully preserving distances from each point to its k nearest neighbors. We show that any metric space can be embedded into with k -local distortion of O ((log k )/ p ). We also show that any ultrametric can be embedded into with k -local distortion 1 + ∊. Our embedding results have immediate applications to local Distance Oracles. We show how to preprocess a graph in polynomial time to obtain a data structure of O ( nk 1/t log 2 k ) bits, such that distance queries from any node to its k nearest neighbors can be answered with stretch O ( t ).

SODA Conference 2008 Conference Paper

Embedding metric spaces in their intrinsic dimension

• Ittai Abraham
• Yair Bartal
• Ofer Neiman

FOCS Conference 2008 Conference Paper

Nearly Tight Low Stretch Spanning Trees

• Ittai Abraham
• Yair Bartal
• Ofer Neiman

We prove that any graph G with n points has a distribution T over spanning trees such that for any edge (u, v) the expected stretch E T~T [d T (u, nu)/d G (u, nu)] is bounded by Otilde(log n). Our result is obtained via a new approach of building "highways" between portals and a new strong diameter probabilistic decomposition theorem.

SODA Conference 2007 Conference Paper

Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion

• Ittai Abraham
• Yair Bartal
• Ofer Neiman

STOC Conference 2007 Conference Paper

Local embeddings of metric spaces

• Ittai Abraham
• Yair Bartal
• Ofer Neiman

In many application areas, complex data sets are often representedby some metric space and metric embedding is used to provide a more structured representation of the data. In many of these applications much greater emphasis is put on the preserving the local structure of the original space than on maintaining its complete structure. This is also the case in some networking applications where "small world" phenomena in communication patterns has been observed. Practical study of embedding has indeed involved with finding embeddings with this property. In this paper we initiate thestudy of local embeddings of metric spaces and provide embeddings with distortion depending solely on the local structureof the space.

STOC Conference 2006 Conference Paper

Advances in metric embedding theory

• Ittai Abraham
• Yair Bartal
• Ofer Neiman

Metric Embedding plays an important role in a vast range of application areas such as computer vision, computational biology, machine learning, networking, statistics, and mathematical psychology, to name a few.The theory of metric embedding received much attention in recent years by mathematicians as well as computer scientists and has been applied in many algorithmic applications.A cornerstone of the field is a celebrated theorem of Bourgain which states that every finite metric space on n points embeds in Euclidean space with O(log n) distortion.Bourgain's result is best possible when considering the worst case distortion over all pairs of points in the metric space. Yet, it is possible that an embedding can do much better in terms of the average distortion .Indeed, in most practical applications of metric embedding the main criteria for the quality of an embedding is its average distortion over all pairs.In this paper we provide an embedding with constant average distortion for arbitrary metric spaces, while maintaining the same worst case bound provided by Bourgain's theorem.In fact, our embedding possesses a much stronger property. We define the l q -distortion of a uniformly distributed pair of points. Our embedding achieves the best possible l q -distortion for all 1 ≤ q ≤ ∞ simultaneously .These results have several algorithmic implications, e.g. an O(1) approximation for the unweighted uncapacitated quadratic assignment problem.The results are based on novel embedding methods which improve on previous methods in another important aspect: the dimension .The dimension of an embedding is of very high importance in particular in applications and much effort has been invested in analyzing it. However, no previous result improved the bound on the dimension which can be derived from Bourgain's embedding.We prove that any metric space on n points embeds into L p with distortion O(log n) in dimension O(log n). This provides an optimal bound on the dimension of the embedding.Somewhat surprisingly, we show that a further small improvement is possible at a small price in the distortion, obtaining an embedding with distortion O(log 1+θ n) in optimal dimension O(θ -1 log n/log log n), for any θ > 0. It is worth noting that with the small loss in the distortion this improves upon the best known embedding of arbitrary spaces into Euclidean space, where dimension reduction is used.Our techniques also allow to obtain the optimal distortion for embedding into L p with nearly tight dimension. For any 1 ≤ p ≤ ⊂ and any 1 ≤ k ≤ p, we give an embedding into L p with distortion O(⌈ log n/k ⌉) in dimension 2 O(k) log n.Underlying our results is a novel embedding method. Probabilistic metric decomposition techniques have played a central role in the field of finite metric embedding in recent years. Here we introduce a novel notion of probabilistic metric decompositions which comes particularly natural in the context of embedding. Our new methodology provides a unified approach to all known results on embedding of arbitrary metric spaces. Moreover, as described above, with some additional ideas they allow to get far stronger results. These metric decompositions seem of independent interest.

FOCS Conference 2005 Conference Paper

Metric Embeddings with Relaxed Guarantees

• Ittai Abraham
• Yair Bartal
• T. -H. Hubert Chan
• Kedar Dhamdhere
• Anupam Gupta 0001
• Jon M. Kleinberg
• Ofer Neiman
• Aleksandrs Slivkins

We consider the problem of embedding finite metrics with slack: we seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be arbitrarily distorted. This definition is motivated by recent research in the networking community, which achieved striking empirical success at embedding Internet latencies with low distortion into low-dimensional Euclidean space, provided that some small slack is allowed. Answering an open question of Kleinberg, Slivkins, and Wexler (2004), we show that provable guarantees of this type can in fact be achieved in general: any finite metric can be embedded, with constant slack and constant distortion, into constant-dimensional Euclidean space. We then show that there exist stronger embeddings into /spl lscr//sub 1/ which exhibit gracefully degrading distortion: these is a single embedding into /spl lscr//sub 1/ that achieves distortion at most O(log 1//spl epsi/) on all but at most an /spl epsi/ fraction of distances, simultaneously for all /spl epsi/ > 0. We extend this with distortion O(log 1//spl epsi/)/sup 1/p/ to maps into general /spl lscr//sub p/, p /spl ges/ 1 for several classes of metrics, including those with bounded doubling dimension and those arising from the shortest-path metric of a graph with an excluded minor. Finally, we show that many of our constructions are tight, and give a general technique to obtain lower bounds for /spl epsi/-slack embeddings from lower bounds for low-distortion embeddings.