Source author record

Michael Elkin

Michael Elkin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Computational Geometry Biomolecules Computational Complexity Molecular Networks quant-ph

Catalog footprint

What is connected

25works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

$(1+ε)$-Approximate Shortest Paths in Dynamic Streams

Computing approximate shortest paths in the dynamic streaming setting is a fundamental challenge that has been intensively studied during the last decade. Currently existing solutions for this problem either build a sparse multiplicative spanner of the input graph and compute shortest paths in the spanner offline, or compute an exact single source BFS tree. Solutions of the first type are doomed to incur a stretch-space tradeoff of $2κ-1$ versus $n^{1+1/κ}$, for an integer parameter $κ$. (In fact, existing solutions also incur an extra factor of $1+ε$ in the stretch for weighted graphs, and an additional factor of $\log^{O(1)}n$ in the space.) The only existing solution of the second type uses $n^{1/2 - O(1/κ)}$ passes over the stream (for space $O(n^{1+1/κ})$), and applies only to unweighted graphs. In this paper we show that $(1+ε)$-approximate single-source shortest paths can be computed in this setting with $\tilde{O}(n^{1+1/κ})$ space using just \emph{constantly} many passes in unweighted graphs, and polylogarithmically many passes in weighted graphs (assuming $ε$ and $κ$ are constant). Moreover, in fact, the same result applies for multi-source shortest paths, as long as the number of sources is $O(n^{1/κ})$. We achieve these results by devising efficient dynamic streaming constructions of $(1 + ε, β)$-spanners and hopsets. We believe that these constructions are of independent interest.

preprint2022arXiv

Almost Shortest Paths with Near-Additive Error in Weighted Graphs

Let $G=(V,E,w)$ be a weighted undirected graph with $n$ vertices and $m$ edges, and fix a set of $s$ sources $S\subseteq V$. We study the problem of computing {\em almost shortest paths} (ASP) for all pairs in $S \times V$ in both classical centralized and parallel (PRAM) models of computation. Consider the regime of multiplicative approximation of $1+ε$, for an arbitrarily small constant $ε> 0$ . In this regime existing centralized algorithms require $Ω(\min\{|E|s,n^ω\})$ time, where $ω< 2.372$ is the matrix multiplication exponent. Existing PRAM algorithms with polylogarithmic depth (aka time) require work $Ω(\min\{|E|s,n^ω\})$. Our centralized algorithm has running time $O((m+ ns)n^ρ)$, and its PRAM counterpart has polylogarithmic depth and work $O((m + ns)n^ρ)$, for an arbitrarily small constant $ρ> 0$. For a pair $(s,v) \in S\times V$, it provides a path of length $\hat{d}(s,v)$ that satisfies $\hat{d}(s,v) \le (1+ε)d_G(s,v) + β\cdot W(s,v)$, where $W(s,v)$ is the weight of the heaviest edge on some shortest $s-v$ path. Hence our additive term depends linearly on a {\em local} maximum edge weight, as opposed to the global maximum edge weight in previous works. Finally, our $β= (1/ρ)^{O(1/ρ)}$. We also extend a centralized algorithm of Dor et al. \cite{DHZ00}. For a parameter $κ= 1,2,\ldots$, this algorithm provides for {\em unweighted} graphs a purely additive approximation of $2(κ-1)$ for {\em all pairs shortest paths} (APASP) in time $\tilde{O}(n^{2+1/κ})$. Within the same running time, our algorithm for {\em weighted} graphs provides a purely additive error of $2(κ- 1) W(u,v)$, for every vertex pair $(u,v) \in {V \choose 2}$, with $W(u,v)$ defined as above. On the way to these results we devise a suit of novel constructions of spanners, emulators and hopsets.

preprint2022arXiv

Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications

This paper presents new deterministic and distributed low-diameter decomposition algorithms for weighted graphs. In particular, we show that if one can efficiently compute approximate distances in a parallel or a distributed setting, one can also efficiently compute low-diameter decompositions. This consequently implies solutions to many fundamental distance based problems using a polylogarithmic number of approximate distance computations. Our low-diameter decomposition generalizes and extends the line of work starting from [Rozhoň, Ghaffari STOC 2020] to weighted graphs in a very model-independent manner. Moreover, our clustering results have additional useful properties, including strong-diameter guarantees, separation properties, restricting cluster centers to specified terminals, and more. Applications include: -- The first near-linear work and polylogarithmic depth randomized and deterministic parallel algorithm for low-stretch spanning trees (LSST) with polylogarithmic stretch. Previously, the best parallel LSST algorithm required $m \cdot n^{o(1)}$ work and $n^{o(1)}$ depth and was inherently randomized. No deterministic LSST algorithm with truly sub-quadratic work and sub-linear depth was known. -- The first near-linear work and polylogarithmic depth deterministic algorithm for computing an $\ell_1$-embedding into polylogarithmic dimensional space with polylogarithmic distortion. The best prior deterministic algorithms for $\ell_1$-embeddings either require large polynomial work or are inherently sequential. Even when we apply our techniques to the classical problem of computing a ball-carving with strong-diameter $O(\log^2 n)$ in an unweighted graph, our new clustering algorithm still leads to an improvement in round complexity from $O(\log^{10} n)$ rounds [Chang, Ghaffari PODC 21] to $O(\log^{4} n)$.

preprint2021arXiv

Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication

Consider an undirected weighted graph $G = (V,E,w)$. We study the problem of computing $(1+ε)$-approximate shortest paths for $S \times V$, for a subset $S \subseteq V$ of $|S| = n^r$ sources, for some $0 < r \le 1$. We devise a significantly improved algorithm for this problem in the entire range of parameter $r$, in both the classical centralized and the parallel (PRAM) models of computation, and in a wide range of $r$ in the distributed (Congested Clique) model. Specifically, our centralized algorithm for this problem requires time $\tilde{O}(|E| \cdot n^{o(1)} + n^{ω(r)})$, where $n^{ω(r)}$ is the time required to multiply an $n^r \times n$ matrix by an $n \times n$ one. Our PRAM algorithm has polylogarithmic time $(\log n)^{O(1/ρ)}$, and its work complexity is $\tilde{O}(|E| \cdot n^ρ+ n^{ω(r)})$, for any arbitrarily small constant $ρ>0$. In particular, for $r \le 0.313\ldots$, our centralized algorithm computes $S \times V$ $(1+ε)$-approximate shortest paths in $n^{2 + o(1)}$ time. Our PRAM polylogarithmic-time algorithm has work complexity $O(|E| \cdot n^ρ+ n^{2+o(1)})$, for any arbitrarily small constant $ρ>0$. Previously existing solutions either require centralized time/parallel work of $O(|E| \cdot |S|)$ or provide much weaker approximation guarantees. In the Congested Clique model, our algorithm solves the problem in polylogarithmic time for $|S| = n^r$ sources, for $r \le 0.655$, while previous state-of-the-art algorithms did so only for $r \le 1/2$. Moreover, it improves previous bounds for all $r > 1/2$. For unweighted graphs, the running time is improved further to $poly(\log\log n)$.

preprint2021arXiv

Improved Weighted Additive Spanners

Graph spanners and emulators are sparse structures that approximately preserve distances of the original graph. While there has been an extensive amount of work on additive spanners, so far little attention was given to weighted graphs. Only very recently [ABSKS20] extended the classical +2 (respectively, +4) spanners for unweighted graphs of size $O(n^{3/2})$ (resp., $O(n^{7/5})$) to the weighted setting, where the additive error is $+2W$ (resp., $+4W$). This means that for every pair $u,v$, the additive stretch is at most $+2W_{u,v}$, where $W_{u,v}$ is the maximal edge weight on the shortest $u-v$ path. In addition, [ABSKS20] showed an algorithm yielding a $+8W_{max}$ spanner of size $O(n^{4/3})$, here $W_{max}$ is the maximum edge weight in the entire graph. In this work we improve the latter result by devising a simple deterministic algorithm for a $+(6+\varepsilon)W$ spanner for weighted graphs with size $O(n^{4/3})$ (for any constant $\varepsilon>0$), thus nearly matching the classical +6 spanner of size $O(n^{4/3})$ for unweighted graphs. Furthermore, we show a $+(2+\varepsilon)W$ subsetwise spanner of size $O(n\cdot\sqrt{|S|})$, improving the $+4W_{max}$ result of [ABSKS20] (that had the same size). We also show a simple randomized algorithm for a $+4W$ emulator of size $\tilde{O}(n^{4/3})$. In addition, we show that our technique is applicable for very sparse additive spanners, that have linear size. For weighted graphs, we use a variant of our simple deterministic algorithm that yields a linear size $+\tilde{O}(\sqrt{n}\cdot W)$ spanner, and we also obtain a tradeoff between size and stretch. Finally, generalizing the technique of [DHZ00] for unweighted graphs, we devise an efficient randomized algorithm producing a $+2W$ spanner for weighted graphs of size $\tilde{O}(n^{3/2})$ in $\tilde{O}(n^2)$ time.

preprint2020arXiv

Near-Additive Spanners and Near-Exact Hopsets, A Unified View

Given an {\em unweighted} undirected graph $G = (V,E)$, and a pair of parameters $ε> 0$, $β= 1,2,\ldots$, a subgraph $G' =(V,H)$, $H \subseteq E$, of $G$ is a {\em $(1+ε,β)$-spanner} (aka, a {\em near-additive spanner}) of $G$ if for every $u,v \in V$, $$d_{G'}(u,v) \le (1+ε)d_G(u,v) + β~.$$ It was shown in \cite{EP01} that for any $n$-vertex $G$ as above, and any $ε> 0$ and $κ= 1,2,\ldots$, there exists a $(1+ε,β)$-spanner $G'$ with $O_{ε,κ}(n^{1+1/κ})$ edges, with $$β= β_{EP} = \left({{\log κ} \over ε}\right)^{\log κ- 2}~.$$ This bound remains state-of-the-art, and its dependence on $ε$ (for the case of small $κ$) was shown to be tight in \cite{ABP18}. Given a {\em weighted} undirected graph $G = (V,E,ω)$, and a pair of parameters $ε> 0$, $β= 1,2,\ldots$, a graph $G'= (V,H,ω')$ is a {\em $(1+ε,β)$-hopset} (aka, a {\em near-exact hopset}) of $G$ if for every $u,v \in V$, $$d_G(u,v) \le d_{G\cup G'}^{(β)}(u,v) \le (1+ε)d_G(u,v)~,$$ where $ d_{G\cup G'}^{(β)}(u,v)$ stands for a $β$-(hop)-bounded distance between $u$ and $v$ in the union graph $G \cup G'$. It was shown in \cite{EN16} that for any $n$-vertex $G$ and $ε$ and $κ$ as above, there exists a $(1+ε,β)$-hopset with $\tilde{O}(n^{1+1/κ})$ edges, with $β= β_{EP}$. Not only the two results of \cite{EP01} and \cite{EN16} are strikingly similar, but so are also their proof techniques. Moreover, Thorup-Zwick's later construction of near-additive spanners \cite{TZ06} was also shown in \cite{EN19,HP17} to provide hopsets with analogous (to that of \cite{TZ06}) properties. In this survey we explore this intriguing phenomenon, sketch the basic proof techniques used for these results, and highlight open questions.

preprint2016arXiv

Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity

We consider coloring problems in the distributed message-passing setting. The previously-known deterministic algorithms for edge-coloring employed at least (2Delta - 1) colors, even though any graph admits an edge-coloring with Delta + 1 colors [V64]. Moreover, the previously-known deterministic algorithms that employed at most O(Delta) colors required superlogarithmic time [B15,BE10,BE11,FHK15]. In the current paper we devise deterministic edge-coloring algorithms that employ only Delta + o(Delta) colors, for a very wide family of graphs. Specifically, as long as the arboricity is a = O(Delta^{1 - ε}), for a constant epsilon > 0, our algorithm computes such a coloring within {polylogarithmic} deterministic time. We also devise significantly improved deterministic edge-coloring algorithms for {general graphs} for a very wide range of parameters. Specifically, for any value $χ$ in the range [4Delta, 2^{o(log Delta)} \cdot Delta], our χ-edge-coloring algorithm has smaller running time than the best previously-known χ-edge-coloring algorithms. Our algorithms are actually much more general, since edge-coloring is equivalent to {vertex-coloring of line graphs.} Our method is applicable to vertex-coloring of the family of graphs with {bounded diversity} that contains line graphs, line graphs of hypergraphs, and many other graphs. Our results are obtained using a novel technique that connects vertices or edges in a certain way that reduces clique size. The resulting structures, which we call {connectors}, can be colored more efficiently than the original graph. Moreover, the color classes constitute simpler subgraphs that can be colored even more efficiently using appropriate connectors. Hence, we recurse until we obtain sufficiently simple structures that are colored directly. We introduce several types of connectors that are useful for various scenarios.

preprint2016arXiv

Distributed Strong Diameter Network Decomposition

For a pair of positive parameters $D,χ$, a partition ${\cal 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 ${\cal G}({\cal P})$, obtained by contracting each of the clusters of ${\cal P}$, can be properly $χ$-colored. The decomposition ${\cal 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 \in {\cal P}$ and every two vertices $u,v \in 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. It was shown by Awerbuch \etal \cite{AGLP89} and Panconesi and Srinivasan \cite{PS92}, that strong $(2^{O(\sqrt{\log n})},2^{O(\sqrt{\log n})})$ network decompositions can be computed in $2^{O(\sqrt{\log n})}$ distributed time. Linial and Saks \cite{LS93} devised an ingenious randomized algorithm that constructs {\em weak} $(O(\log n),O(\log n))$ network decompositions in $O(\log^2 n)$ time. It was however open till now if {\em strong} network decompositions with both parameters $2^{o(\sqrt{\log n})}$ can be constructed in distributed $2^{o(\sqrt{\log n})}$ time. In this paper we answer this long-standing open question in the affirmative, and show that strong $(O(\log n),O(\log n))$ network decompositions can be computed in $O(\log^2 n)$ time. 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 \etal \cite{BGKMPT11}, and Miller \etal \cite{MPX13}. These authors developed this approach for PRAM algorithms for padded partitions. We adapt their approach to network decompositions in the distributed model of computation.

preprint2016arXiv

Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths

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 \cite[JACM 2000]{C00} 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 \cite{C00} devised efficient algorithms for constructing hopsets with {\em 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 {\em 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 \cite{C00}, 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$.

preprint2016arXiv

On Efficient Distributed Construction of Near Optimal Routing Schemes

Given a distributed network represented by a weighted undirected graph $G=(V,E)$ on $n$ vertices, and a parameter $k$, we devise a distributed algorithm that computes a routing scheme in $(n^{1/2+1/k}+D)\cdot n^{o(1)}$ rounds, where $D$ is the hop-diameter of the network. The running time matches the lower bound of $\tildeΩ(n^{1/2}+D)$ rounds (which holds for any scheme with polynomial stretch), up to lower order terms. The routing tables are of size $\tilde{O}(n^{1/k})$, the labels are of size $O(k\log^2n)$, and every packet is routed on a path suffering stretch at most $4k-5+o(1)$. Our construction nearly matches the state-of-the-art for routing schemes built in a centralized sequential manner. The previous best algorithms for building routing tables in a distributed small messages model were by \cite[STOC 2013]{LP13} and \cite[PODC 2015]{LP15}. The former has similar properties but suffers from substantially larger routing tables of size $O(n^{1/2+1/k})$, while the latter has sub-optimal running time of $\tilde{O}(\min\{(nD)^{1/2}\cdot n^{1/k},n^{2/3+2/(3k)}+D\})$.

preprint2016arXiv

Terminal Embeddings

In this paper we study {\em terminal embeddings}, in which one is given a finite metric $(X,d_X)$ (or a graph $G=(V,E)$) and a subset $K \subseteq X$ of its points are designated as {\em 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 $\approx|K|\cdot |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 {\em 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 \times X$ and with respect to $K \times X$. Moreover, our embeddings have implications to the areas of Approximation and Online Algorithms. In particular, [ALN08] devised an $\tilde{O}(\sqrt{\log r})$-approximation algorithm for sparsest-cut instances with $r$ demands. Building on their framework, we provide an $\tilde{O}(\sqrt{\log |K|})$-approximation for sparsest-cut instances in which each demand is incident on one of the vertices of $K$ (aka, terminals). Since $|K| \le r$, our bound generalizes that of [ALN08].

preprint2015arXiv

A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs

In 2001 Thorup and Zwick devised a distance oracle, which given an $n$-vertex undirected graph and a parameter $k$, has size $O(k n^{1+1/k})$. Upon a query $(u,v)$ their oracle constructs a $(2k-1)$-approximate path $Π$ between $u$ and $v$. The query time of the Thorup-Zwick's oracle is $O(k)$, and it was subsequently improved to $O(1)$ by Chechik. A major drawback of the oracle of Thorup and Zwick is that its space is $Ω(n \cdot \log n)$. Mendel and Naor devised an oracle with space $O(n^{1+1/k})$ and stretch $O(k)$, but their oracle can only report distance estimates and not actual paths. In this paper we devise a path-reporting distance oracle with size $O(n^{1+1/k})$, stretch $O(k)$ and query time $O(n^ε)$, for an arbitrarily small $ε> 0$. In particular, our oracle can provide logarithmic stretch using linear size. Another variant of our oracle has size $O(n \log\log n)$, polylogarithmic stretch, and query time $O(\log\log n)$. For unweighted graphs we devise a distance oracle with multiplicative stretch $O(1)$, additive stretch $O(β(k))$, for a function $β(\cdot)$, space $O(n^{1+1/k} \cdot β)$, and query time $O(n^ε)$, for an arbitrarily small constant $ε>0$. The tradeoff between multiplicative stretch and size in these oracles is far below girth conjecture threshold (which is stretch $2k-1$ and size $O(n^{1+1/k})$). Breaking the girth conjecture tradeoff is achieved by exhibiting a tradeoff of different nature between additive stretch $β(k)$ and size $O(n^{1+1/k})$. A similar type of tradeoff was exhibited by a construction of $(1+ε,β)$-spanners due to Elkin and Peleg. However, so far $(1+ε,β)$-spanners had no counterpart in the distance oracles' world. An important novel tool that we develop on the way to these results is a {distance-preserving path-reporting oracle}.

preprint2015arXiv

Prioritized Metric Structures and Embedding

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 \cite{llr}, online algorithms \cite{BBMN11}, distributed algorithms \cite{KKMPT12} and for computing sparsifiers \cite{ST04}. 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. In this paper we alleviate this limitation by devising a suit of {\em prioritized} metric data structures and embeddings. We show that given a priority ranking $(x_1,x_2,\ldots,x_n)$ of the graph vertices (respectively, metric points) one can devise a metric data structure (respectively, embedding) in which the stretch (resp., distortion) incurred by any pair containing a vertex $x_j$ will depend on the rank $j$ of the vertex. We also show that other important parameters, such as the label size and (in some sense) the dimension, may depend only on $j$. In some of our metric data structures (resp., embeddings) we achieve both prioritized stretch (resp., distortion) and label size (resp., dimension) {\em simultaneously}. The worst-case performance of our metric data structures and embeddings is typically asymptotically no worse than of their non-prioritized counterparts.

preprint2015arXiv

The Locality of Distributed Symmetry Breaking

Symmetry breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this paper we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes - An MIS algorithm running in $O(\log^2Δ+ 2^{O(\sqrt{\log\log n})})$ time, where $Δ$ is the maximum degree. This is the first MIS algorithm to improve on the 1986 algorithms of Luby and Alon, Babai, and Itai, when $\log n \ll Δ\ll 2^{\sqrt{\log n}}$, and comes close to the $Ω(\log Δ)$ lower bound of Kuhn, Moscibroda, and Wattenhofer. - A maximal matching algorithm running in $O(\logΔ+ \log^4\log n)$ time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on $Δ$ is provably optimal. - A method for reducing symmetry breaking problems in low arboricity/degeneracy graphs to low degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an $O(\sqrt{\log n})$-time maximal matching algorithm for graphs with arboricity up to $2^{\sqrt{\log n}}$ and an $O(\log^{2/3} n)$-time MIS algorithm for graphs with arboricity up to $2^{(\log n)^{1/3}}$. Each of our algorithms is based on a simple, but powerful technique for reducing a randomized symmetry breaking task to a corresponding deterministic one on a poly$(\log n)$-size graph.

preprint2014arXiv

Can Quantum Communication Speed Up Distributed Computation?

The focus of this paper is on {\em quantum distributed} computation, where we investigate whether quantum communication can help in {\em speeding up} distributed network algorithms. Our main result is that for certain fundamental network problems such as minimum spanning tree, minimum cut, and shortest paths, quantum communication {\em does not} help in substantially speeding up distributed algorithms for these problems compared to the classical setting. In order to obtain this result, we extend the technique of Das Sarma et al. [SICOMP 2012] to obtain a uniform approach to prove non-trivial lower bounds for quantum distributed algorithms for several graph optimization (both exact and approximate versions) as well as verification problems, some of which are new even in the classical setting, e.g. tight randomized lower bounds for Hamiltonian cycle and spanning tree verification, answering an open problem of Das Sarma et al., and a lower bound in terms of the weight aspect ratio, matching the upper bounds of Elkin [STOC 2004]. Our approach introduces the {\em Server model} and {\em Quantum Simulation Theorem} which together provide a connection between distributed algorithms and communication complexity. The Server model is the standard two-party communication complexity model augmented with additional power; yet, most of the hardness in the two-party model is carried over to this new model. The Quantum Simulation Theorem carries this hardness further to quantum distributed computing. Our techniques, except the proof of the hardness in the Server model, require very little knowledge in quantum computing, and this can help overcoming a usual impediment in proving bounds on quantum distributed algorithms.

preprint2014arXiv

Light Spanners

A $t$-spanner of a weighted undirected graph $G=(V,E)$, is a subgraph $H$ such that $d_H(u,v)\le t\cdot d_G(u,v)$ for all $u,v\in V$. The sparseness of the spanner can be measured by its size (the number of edges) and weight (the sum of all edge weights), both being important measures of the spanner's quality -- in this work we focus on the latter. Specifically, it is shown that for any parameters $k\ge 1$ and $ε>0$, any weighted graph $G$ on $n$ vertices admits a $(2k-1)\cdot(1+ε)$-stretch spanner of weight at most $w(MST(G))\cdot O_ε(kn^{1/k}/\log k)$, where $w(MST(G))$ is the weight of a minimum spanning tree of $G$. Our result is obtained via a novel analysis of the classic greedy algorithm, and improves previous work by a factor of $O(\log k)$.

preprint2014arXiv

Optimizing Budget Allocation in Graphs

In the classical facility location problem we consider a graph $G$ with fixed weights on the edges of $G$. The goal is then to find an optimal positioning for a set of facilities on the graph with respect to some objective function. We introduce a new framework for facility location problems, where the weights on the graph edges are not fixed, but rather should be assigned. The goal is to find a valid assignment for which the resulting weighted graph optimizes the facility location objective function. We present algorithms for finding the optimal {\em budget allocation} for the center point problem and for the median point problem on trees. Our algorithms run in linear time, both for the case where a candidate vertex is given as part of the input, and for the case where finding a vertex that optimizes the solution is part of the problem. We also present a hardness result for the general graph case of the center point problem, followed by an $O(\log^2(n))$ approximation algorithm on graphs - with general metric spaces.

preprint2014arXiv

Space-Efficient Path-Reporting Approximate Distance Oracles

We consider approximate {\em path-reporting} distance oracles, distance labeling and labeled routing with extremely low space requirement, for general undirected graphs. For distance oracles, we show how to break the n\log n space bound of Thorup and Zwick if approximate {\em 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.

preprint2012arXiv

Energy fluctuations shape free energy of nonspecific biomolecular interactions

Understanding design principles of biomolecular recognition is a key question of molecular biology. Yet the enormous complexity and diversity of biological molecules hamper the efforts to gain a predictive ability for the free energy of protein-protein, protein-DNA, and protein-RNA binding. Here, using a variant of the Derrida model, we predict that for a large class of biomolecular interactions, it is possible to accurately estimate the relative free energy of binding based on the fluctuation properties of their energy spectra, even if a finite number of the energy levels is known. We show that the free energy of the system possessing a wider binding energy spectrum is almost surely lower compared with the system possessing a narrower energy spectrum. Our predictions imply that low-affinity binding scores, usually wasted in protein-protein and protein-DNA docking algorithms, can be efficiently utilized to compute the free energy. Using the results of Rosetta docking simulations of protein-protein interactions from Andre et al., Proc. Natl. Acad. Sci. U.S.A. 105, 16148 (2008), we demonstrate the power of our predictions.

preprint2012arXiv

Fast Constructions of Light-Weight Spanners for General Graphs

To our knowledge, there are only two known algorithms for constructing sparse and light spanners for general graphs. One of them is the greedy algorithm of Alth$\ddot{o}$fer et al. \cite{ADDJS93}, analyzed by Chandra et al. in SoCG'92. The greedy algorithm consructs, for every \emph{weighted} undirected $n$-vertex $m$-edge graph $G = (V,E)$ and any integer $k \ge 1$, a $(2k-1)$-spanner with $O(n^{1 + 1/k})$ edges and weight $O(k \cdot n^{(1+\eps)/k}) \cdot ω(MST(G))$, for any $\eps > 0$. The drawback of the greedy algorithm is that it requires $O(m \cdot (n^{1 + 1/k} + n \cdot \log n))$ time. The other algorithm is due to Awerbuch et al. \cite{ABP91}. It constructs $O(k)$-spanners with $O(k \cdot n^{1 + 1/k} \cdot Λ)$ edges, weight $O(k^2 \cdot n^{1/k} \cdot Λ) \cdot ω(MST(G))$, within time $O(m \cdot k \cdot n^{1/k} \cdot Λ)$, where $Λ$ is the logarithm of the aspect ratio of the graph. The running time of both these algorithms is unsatisfactory. Moreover, the usually faster algorithm of \cite{ABP91} pays for the speedup by significantly increasing both the stretch, the sparsity, and the weight of the resulting spanner. In this paper we devise an efficient algorithm for constructing sparse and light spanners. Specifically, our algorithm constructs $((2k-1) \cdot (1+\eps))$-spanners with $O(k \cdot n^{1 + 1/k})$ edges and weight $O(k \cdot n^{1/k}) \cdot ω(MST(G))$, where $\eps > 0$ is an arbitrarily small constant. The running time of our algorithm is $O(k \cdot m + \min\{n \cdot \log n,m \cdot α(n)\})$. Moreover, by slightly increasing the running time we can reduce the other parameters. These results address an open problem from the ESA'04 paper by Roditty and Zwick \cite{RZ04}.

preprint2012arXiv

Optimal Euclidean spanners: really short, thin and lanky

In a seminal STOC'95 paper, titled "Euclidean spanners: short, thin and lanky", Arya et al. devised a construction of Euclidean $(1+\eps)$-spanners that achieves constant degree, diameter $O(\log n)$, and weight $O(\log^2 n) \cdot ω(MST)$, and has running time $O(n \cdot \log n)$. This construction applies to $n$-point constant-dimensional Euclidean spaces. Moreover, Arya et al. conjectured that the weight bound can be improved by a logarithmic factor, without increasing the degree and the diameter of the spanner, and within the same running time. This conjecture of Arya et al. became a central open problem in the area of Euclidean spanners. In this paper we resolve the long-standing conjecture of Arya et al. in the affirmative. Specifically, we present a construction of spanners with the same stretch, degree, diameter, and running time, as in Arya et al.'s result, but with optimal weight $O(\log n) \cdot ω(MST)$. Moreover, our result is more general in three ways. First, we demonstrate that the conjecture holds true not only in constant-dimensional Euclidean spaces, but also in doubling metrics. Second, we provide a general tradeoff between the three involved parameters, which is tight in the entire range. Third, we devise a transformation that decreases the lightness of spanners in general metrics, while keeping all their other parameters in check. Our main result is obtained as a corollary of this transformation.

preprint2011arXiv

Balancing Degree, Diameter and Weight in Euclidean Spanners

In this paper we devise a novel \emph{unified} construction of Euclidean spanners that trades between the maximum degree, diameter and weight gracefully. For a positive integer k, our construction provides a (1+eps)-spanner with maximum degree O(k), diameter O(log_k n + alpha(k)), weight O(k \cdot log_k n \cdot log n) \cdot w(MST(S)), and O(n) edges. Note that for k= n^{1/alpha(n)} this gives rise to diameter O(alpha(n)), weight O(n^{1/alpha(n)} \cdot log n \cdot alpha(n)) \cdot w(MST(S)) and maximum degree O(n^{1/alpha(n)}), which improves upon a classical result of Arya et al. \cite{ADMSS95}; in the corresponding result from \cite{ADMSS95} the spanner has the same number of edges and diameter, but its weight and degree may be arbitrarily large. Also, for k = O(1) this gives rise to maximum degree O(1), diameter O(log n) and weight O(log^2 n) \cdot w(MST(S)), which reproves another classical result of Arya et al. \cite{ADMSS95}. Our bound of O(log_k n + alpha(k)) on the diameter is optimal under the constraints that the maximum degree is O(k) and the number of edges is O(n). Our bound on the weight is optimal up to a factor of log n. Our construction also provides a similar tradeoff in the complementary range of parameters, i.e., when the weight should be smaller than log^2 n, but the diameter is allowed to grow beyond log n. For random point sets in the d-dimensional unit cube, we "shave" a factor of log n from the weight bound. Specifically, in this case our construction achieves maximum degree O(k), diameter O(log_k n + alpha(k)) and weight that is with high probability O(k \cdot log_k n) \cdot w(MST(S)). Finally, en route to these results we devise optimal constructions of 1-spanners for general tree metrics, which are of independent interest.

preprint2010arXiv

Deterministic Distributed Vertex Coloring in Polylogarithmic Time

Consider an n-vertex graph G = (V,E) of maximum degree Delta, and suppose that each vertex v \in V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, i.e., it proceeds in discrete rounds. In the distributed vertex coloring problem the objective is to color G with Delta + 1, or slightly more than Delta + 1, colors using as few rounds of communication as possible. (The number of rounds of communication will be henceforth referred to as running time.) Efficient randomized algorithms for this problem are known for more than twenty years \cite{L86, ABI86}. Specifically, these algorithms produce a (Delta + 1)-coloring within O(log n) time, with high probability. On the other hand, the best known deterministic algorithm that requires polylogarithmic time employs O(Delta^2) colors. This algorithm was devised in a seminal FOCS'87 paper by Linial \cite{L87}. Its running time is O(log^* n). In the same paper Linial asked whether one can color with significantly less than Delta^2 colors in deterministic polylogarithmic time. By now this question of Linial became one of the most central long-standing open questions in this area. In this paper we answer this question in the affirmative, and devise a deterministic algorithm that employs Δ^{1 +o(1)} colors, and runs in polylogarithmic time. Specifically, the running time of our algorithm is O(f(Delta) log Delta log n), for an arbitrarily slow-growing function f(Delta) = ω(1). We can also produce O(Delta^{1 + η})-coloring in O(log Delta log n)-time, for an arbitrarily small constant η> 0, and O(Delta)-coloring in O(Delta^ε log n) time, for an arbitrarily small constant ε> 0.

preprint2010arXiv

Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence

We study the {edge-coloring} problem in the message-passing model of distributed computing. This is one of the most fundamental and well-studied problems in this area. Currently, the best-known deterministic algorithms for (2Delta -1)-edge-coloring requires O(Delta) + log-star n time \cite{PR01}, where Delta is the maximum degree of the input graph. Also, recent results of \cite{BE10} for vertex-coloring imply that one can get an O(Delta)-edge-coloring in O(Delta^{epsilon} \cdot \log n) time, and an O(Delta^{1 + epsilon})-edge-coloring in O(log Delta log n) time, for an arbitrarily small constant epsilon > 0. In this paper we devise a drastically faster deterministic edge-coloring algorithm. Specifically, our algorithm computes an O(Delta)-edge-coloring in O(Delta^{epsilon}) + log-star n time, and an O(Delta^{1 + epsilon})-edge-coloring in O(log Delta) + log-star n time. This result improves the previous state-of-the-art {exponentially} in a wide range of Delta, specifically, for 2^{Omega(\log-star n)} \leq Delta \leq polylog(n). In addition, for small values of Delta our deterministic algorithm outperforms all the existing {randomized} algorithms for this problem. On our way to these results we study the {vertex-coloring} problem on the family of graphs with bounded {neighborhood independence}. This is a large family, which strictly includes line graphs of r-hypergraphs for any r = O(1), and graphs of bounded growth. We devise a very fast deterministic algorithm for vertex-coloring graphs with bounded neighborhood independence. This algorithm directly gives rise to our edge-coloring algorithms, which apply to {general} graphs. Our main technical contribution is a subroutine that computes an O(Delta/p)-defective p-vertex coloring of graphs with bounded neighborhood independence in O(p^2) + \log-star n time, for a parameter p, 1 \leq p \leq Delta.

preprint2008arXiv

Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners

We show that for every $n$-point metric space $M$ there exists a spanning tree $T$ with unweighted diameter $O(\log n)$ and weight $ω(T) = O(\log n) \cdot ω(MST(M))$. Moreover, there is a designated point $rt$ such that for every point $v$, $dist_T(rt,v) \le (1+ε) \cdot dist_M(rt,v)$, for an arbitrarily small constant $ε> 0$. We extend this result, and provide a tradeoff between unweighted diameter and weight, and prove that this tradeoff is \emph{tight up to constant factors} in the entire range of parameters. These results enable us to settle a long-standing open question in Computational Geometry. In STOC'95 Arya et al. devised a construction of Euclidean Spanners with unweighted diameter $O(\log n)$ and weight $O(\log n) \cdot ω(MST(M))$. Ten years later in SODA'05 Agarwal et al. showed that this result is tight up to a factor of $O(\log \log n)$. We close this gap and show that the result of Arya et al. is tight up to constant factors.

Michael Elkin

What is connected

Connect this record

See the researcher in context

Building this map preview

25 published item(s)

$(1+ε)$-Approximate Shortest Paths in Dynamic Streams

Almost Shortest Paths with Near-Additive Error in Weighted Graphs

Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications

Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication

Improved Weighted Additive Spanners

Near-Additive Spanners and Near-Exact Hopsets, A Unified View

Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity

Distributed Strong Diameter Network Decomposition

Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths

On Efficient Distributed Construction of Near Optimal Routing Schemes

Terminal Embeddings

A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs

Prioritized Metric Structures and Embedding

The Locality of Distributed Symmetry Breaking

Can Quantum Communication Speed Up Distributed Computation?

Light Spanners

Optimizing Budget Allocation in Graphs

Space-Efficient Path-Reporting Approximate Distance Oracles

Energy fluctuations shape free energy of nonspecific biomolecular interactions

Fast Constructions of Light-Weight Spanners for General Graphs

Optimal Euclidean spanners: really short, thin and lanky

Balancing Degree, Diameter and Weight in Euclidean Spanners

Deterministic Distributed Vertex Coloring in Polylogarithmic Time

Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence

Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners