Arrow Research search

Author name cluster

Ofer Neiman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

24 papers
2 author rows

Possible papers

24

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.

Details DOI

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.

PDF Details

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.

Details

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].

Details DOI

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.

Details

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.

Details

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.

Details DOI

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 .

Details

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.

Details DOI

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.

Details

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.

Details

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 ).

Details

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.

Details

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.

Details

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.

Details