In this paper we consider the problem of approximating Euclidean distances by the infinite integer grid graph. Although the topology of the graph is fixed, we have control over the edge-weight assignment $w:E\to \mathbb{R}_{\ge 0}$, and hope to have grid distances be asymptotically isometric to Euclidean distances, that is, for all grid points $u,v$, $\mathrm{dist}_w(u,v) = (1\pm o(1))\|u-v\|_2$. We give three methods for solving this problem, each attractive in its own way. * Our first construction is based on an embedding of the recursive, non-periodic pinwheel tiling of Radin and Conway into the integer grid. Distances in the pinwheel graph are asymptotically isometric to Euclidean distances, but no explicit bound on the rate of convergence was known. We prove that the multiplicative distortion of the pinwheel graph is $(1+1/Θ(\log^ξ\log D))$, where $D$ is the Euclidean distance and $ξ=Θ(1)$. The pinwheel tiling approach is conceptually simple, but can be improved quantitatively. * Our second construction is based on a hierarchical arrangement of "highways." It is simple, achieving stretch $(1 + 1/Θ(D^{1/9}))$, which converges doubly exponentially faster than the pinwheel tiling approach. * The first two methods are deterministic. An even simpler approach is to sample the edge weights independently from a common distribution $\mathscr{D}$. Whether there exists a distribution $\mathscr{D}^*$ that makes grid distances Euclidean, asymptotically and in expectation, is major open problem in the theory of first passage percolation. Previous experiments show that when $\mathscr{D}$ is a Fisher distribution, grid distances are within 1\% of Euclidean. We demonstrate experimentally that this level of accuracy can be achieved by a simple 2-point distribution that assigns weights 0.41 or 4.75 with probability 44\% and 56\%, respectively.

For a fixed positive integer \(k\), two players, \(\textsf {Builder}\) and \(\textsf {Chooser}\), alternate turns playing the following game on a dynamically changing graph that is initially empty. In each round, \(\textsf {Builder}\) introduces a new vertex with edges to all previous vertices and then partitions the entire edge set into two subsets, after which \(\textsf {Chooser}\) deletes one of the two. \(\textsf {Builder}\) attempts to build a clique of size \(k\), while \(\textsf {Chooser}\) attempts to prevent that. We prove tower-type upper and lower bounds on how many rounds \(\textsf {Builder}\) needs to guarantee a \(k\)-clique.

We aim to revive Thorup’s conjecture [Thorup, WG’92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph G=(V,E) with m edges, we can add m1+o(1) “shortcut” edges E+ from the transitive closure E* of G so that G+(u,v) ≤ mo(1) for all (u,v)∈ E*, where G+=(V,E∪ E+). The conjecture was refuted by Hesse [Hesse, SODA’03], followed by significant efforts in the last few years to optimize the lower bounds.

In the Contention Resolution problem n parties each wish to have exclusive use of a shared resource for one unit of time. A canonical example is n devices that each must broadcast a packet of information on a shared channel, but the same principles apply to other distributed systems. The problem has been studied since the early 1970s, under a variety of assumptions on feedback (collision detection, etc.) given to the parties, how the parties wake up (synchronized, adversarial, random), knowledge of n, and so on. The most consistent assumption is that parties do not have access to a global clock, only their local time since wake-up. This is surprising because the assumption of a global clock is both technologically realistic and algorithmically interesting. It enriches the problem, and opens the door to entirely new techniques.

Abstract. A [Formula: see text]- vertex connectivity oracle for an undirected graph [Formula: see text] is a data structure that, given [Formula: see text], reports [Formula: see text], where [Formula: see text] is the pairwise vertex connectivity between [Formula: see text]. There are three main measures of efficiency: construction time, query time, and space. Prior work of Izsak and Nutov [ Inform. Process. Lett., 112 (2012), pp. 39–43] produced a data structure of [Formula: see text] words, which can even be encoded as a [Formula: see text]-bit labeling scheme, that can answer vertex connectivity queries in [Formula: see text] time. The construction time is polynomial but unspecified. In this paper, we address the top three complexity measures. (1) Space: We prove that any [Formula: see text]-vertex connectivity oracle requires [Formula: see text] bits of space for any [Formula: see text]. This proves that the Iszak–Nutov data structure is optimal up to polylogarithmic factors for every [Formula: see text] and that the sparsifiers of Nagamochi and Ibaraki [ Algorithmica, 7 (1992), pp. 583–596] are optimal compression schemes for [Formula: see text]-vertex connectivity up to a logarithmic factor. In particular, whereas all edge connectivities can be efficiently compressed (as a weighted [Formula: see text]-edge Gomory–Hu tree), vertex connectivity admits no asymptotic compression: [Formula: see text] bits are necessary. We design a variation on Izsak and Nutov’s data structure that uses [Formula: see text] words of space. (2) Query time: We answer queries in [Formula: see text] time, improving on the [Formula: see text] time bound of Izsak and Nutov [ Inform. Process. Lett., 112 (2012), pp. 39–43]. The main idea is to build instances of [Formula: see text] data structures, with additional structure based on affine planes. This structure allows for query time that is linear in the output size, which evades some conditional lower bounds that are polynomial in the query set sizes [ 42 , 51 ]. (3) Construction time: Our data structure can be constructed in the time of [Formula: see text] max-flow computations, namely, [Formula: see text] time, using the recent near-linear time flow algorithm of [ 13 ]. The main technical contribution here is a fast algorithm to compute a [Formula: see text]-approximate Gomory–Hu tree for element connectivity in the time of [Formula: see text] max-flow computations. Element connectivity is a notion that generalizes edge and vertex connectivity.

In the d-dimensional turnstile streaming model, a frequency vector 𝐱 = (𝐱(1),…,𝐱(n)) ∈ (ℝ^d)ⁿ is updated entry-wisely over a stream. We consider the problem of f-moment estimation for which one wants to estimate f(𝐱)=∑_{v ∈ [n]}f(𝐱(v)) with a small-space sketch. A function f is tractable if the f-moment can be estimated to within a constant factor using polylog(n) space. The f-moment estimation problem has been intensively studied in the d = 1 case. Flajolet and Martin estimate the F₀-moment (f(x) = 1 (x > 0), incremental stream); Alon, Matias, and Szegedy estimate the L₂-moment (f(x) = x²); Indyk estimates the L_α-moment (f(x) = |x|^α), α ∈ (0,2]. For d ≥ 2, Ganguly, Bansal, and Dube estimate the L_{p,q} hybrid moment (f:ℝ^d → ℝ,f(x) = (∑_{j = 1}^d |x_j|^p)^q), p ∈ (0,2],q ∈ (0,1). For tractability, Bar-Yossef, Jayram, Kumar, and Sivakumar show that f(x) = |x|^α is not tractable for α > 2. Braverman, Chestnut, Woodruff, and Yang characterize the class of tractable one-variable functions except for a class of nearly periodic functions. In this work we present a simple and generic scheme to construct sketches with the novel idea of hashing indices to Lévy processes, from which one can estimate the f-moment f(𝐱) where f is the characteristic exponent of the Lévy process. The fundamental Lévy-Khintchine representation theorem completely characterizes the space of all possible characteristic exponents, which in turn characterizes the set of f-moments that can be estimated by this generic scheme. The new scheme has strong explanatory power. It unifies the construction of many existing sketches (F₀, L₀, L₂, L_α, L_{p,q}, etc.) and it implies the tractability of many nearly periodic functions that were previously unclassified. Furthermore, the scheme can be conveniently generalized to multidimensional cases (d ≥ 2) by considering multidimensional Lévy processes and can be further generalized to estimate heterogeneous moments by projecting different indices with different Lévy processes. We conjecture that the set of tractable functions can be characterized using the Lévy-Khintchine representation theorem via what we called the Fourier-Hahn-Lévy method.

We consider the problem of assigning short labels to the vertices and edges of a graph G so that given any query 〈s, t, F 〉 with |F | ≤ f, we can determine whether s and t are still connected in G — F, given only the labels of F ∪ {s, t }.

Given G : ℝ+ → ℝ+, the G-moment of a vector x ∈ ℝ+n is and the G-sampling problem is to select an index v* ∈ [n] according to its contribution to the G-moment, i.e., such that ℙ(v * = v) = G (x(v ))/G (x). Approximate G -samplers may introduce multiplicative and/or additive errors to this probability, and some have a non-trivial probability of failure.

Detecting the elements of deception in a conversation is one of the most challenging problems for the AI community. It becomes even more difficult to design a transparent system, which is fully explainable and satisfies the need for financial and legal services to be deployed. This paper presents an approach for fraud detection in transcribed telephone conversations using linguistic features. The proposed approach exploits the syntactic and semantic information of the transcription to extract both the linguistic markers and the sentiment of the customer's response. We demonstrate the results on real-world financial services data using simple, robust and explainable classifiers such as Naive Bayes, Decision Tree, Nearest Neighbours, and Support Vector Machines.

We consider the problem of comparison-sorting an n-permutation S that avoids some k-permutation π. Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak [CGK + 15b] prove that when S is sorted by inserting the elements into the GreedyFuture [DHI+09] binary search tree, the running time is linear in the extremal function Ex(Pπ ⊗ (∴), n). This is the maximum number of 1s in an n × n 0-1 matrix avoiding Pπ ⊗ (∴), where Pπ is the k × k permutation matrix of π, and Pπ ⊗ (∴) is the 2k × 3k Kronecker product of Pπ and the “hat” pattern (∴). The same time bound can be achieved by sorting S with Kozma and Saranurak's SmoothHeap [KS20].

The extremal theory of forbidden 0-1 matrices studies the asymptotic growth of the function Ex(P, n), which is the maximum weight of a matrix A ∈ {0,1}n×n whose submatrices avoid a fixed pattern P ∈ {0, 1}k×1. This theory has been wildly successful at resolving problems in combinatorics [Kla00, MT04, CK12], discrete and computational geometry [Für90, Agg15, ES96, PS91, Mit92, BG91], structural graph theory [GM14, BGK+21, BKTW22] and the analysis of data structures [Pet10, KS20], particularly corollaries of the dynamic optimality conjecture [CGK + 15b, CGK + 15a, CGJ+23, CPY24].

We present succinct labeling schemes for answering connectivity queries in graphs subject to a specified number of vertex failures. An f-vertex/edge fault tolerant (f-V/EFT) connectivity labeling is a scheme that produces succinct labels for the vertices (and possibly to the edges) of an n-vertex graph G, such that given only the labels of two vertices s,t and of at most f faulty vertices/edges F, one can infer if s and t are connected in G−F. The primary complexity measure is the maximum label length (in bits). The f-EFT setting is relatively well understood: [Dory and Parter, PODC 2021] gave a randomized scheme with succinct labels of O(log3 n) bits, which was subsequently derandomized by [Izumi et al., PODC 2023] with Õ(f2)-bit labels. As both noted, handling vertex faults is more challenging. The known bounds for the f-VFT setting are far away: [Parter and Petruschka, DISC 2022] gave Õ(n1−1/2Θ(f))-bit labels, which is linear in n already for f =Ω(loglogn). In this work we present an efficient f-VFT connectivity labeling scheme using poly(f, logn) bits. Specifically, we present a randomized scheme with O(f3 log5 n)-bit labels, and a derandomized version with O(f7 log13 n)-bit labels, compared to an Ω(f)-bit lower bound on the required label length. Our schemes are based on a new low-degree graph decomposition that improves on [Duan and Pettie, SODA 2017], and facilitates its distributed representation into labels. This is accompanied with specialized linear graph sketches that extend the techniques of the Dory and Parter to the vertex fault setting, which are derandomized by adapting the approach of Izumi et al. and combining it with hit-miss hash families of [Karthik and Parter, SODA 2021]. Finally, we show that our labels naturally yield routing schemes avoiding a given set of at most f vertex failures with table and header sizes of only poly(f,logn) bits. This improves significantly over the linear size bounds implied by the EFT routing scheme of Dory and Parter.

Since the mid-1980s it has been known that Byzantine Agreement can be solved with probability 1 asynchronously, even against an omniscient, computationally unbounded adversary that can adaptively corrupt up to f < n/3 parties. Moreover, the problem is insoluble with f ≥ n/3 corruptions. However, Bracha’s [ 13 ] 1984 protocol (see also Ben-Or [ 8 ]) achieved f < n/3 resilience at the cost of exponential expected latency 2 Θ ( n ) , a bound that has never been improved in this model with f = ⌊ (n-1)/3 ⌋ corruptions. In this article, we prove that Byzantine Agreement in the asynchronous, full information model can be solved with probability 1 against an adaptive adversary that can corrupt f < n/3 parties, while incurring only polynomial latency with high probability . Our protocol follows an earlier polynomial latency protocol of King and Saia [ 33 , 34 ], which had suboptimal resilience, namely f ≈ n /10 9 [ 33 , 34 ]. Resilience f = (n-1)/3 is uniquely difficult, as this is the point at which the influence of the Byzantine and honest players are of roughly equal strength. The core technical problem we solve is to design a collective coin-flipping protocol that eventually lets us flip a coin with an unambiguous outcome. In the beginning, the influence of the Byzantine players is too powerful to overcome, and they can essentially fix the coin’s behavior at will. We guarantee that after just a polynomial number of executions of the coin-flipping protocol, either (a) the Byzantine players fail to fix the behavior of the coin (thereby ending the game) or (b) we can “blacklist” players such that the blacklisting rate for Byzantine players is at least as large as the blacklisting rate for good players. The blacklisting criterion is based on a simple statistical test of fraud detection .

Cardinality Estimation (aka Distinct Elements) is a classic problem in sketching with many applications in databases, networking, and security. Although sketching algorithms are fairly simple, analyzing the cardinality estimators is notoriously difficult, and even today the analyses of state-of-the-art sketches like HyperLogLog and ¶CSA are not very accessible.

Since the mid-1980s it has been known that Byzantine Agreement can be solved with probability 1 asynchronously, even against an omniscient, computationally unbounded adversary that can adaptively corrupt up to f < n/3 parties. Moreover, the problem is insoluble with f ≥ n/3 corruptions. However, Bracha's [Bra87] 1984 protocol (see also Ben-Or [Ben83]) achieved f < n/3 resilience at the cost of exponential expected latency 2θ(n), a bound that has never been improved in this model with f = ⌊(n- 1)/3⌋ corruptions.

We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between space S and query time Q , and since the mid-1990s all results had polynomial time-space tradeoffs, e.g., Q = ~ Θ( n/√ S ) or Q = ~Θ( n 5/2 /S 3/2 ). In this article we show that there is no polynomial tradeoff between time and space and that it is possible to simultaneously achieve almost optimal space n 1+ o (1) and almost optimal query time n o (1) . More precisely, we achieve the following space-time tradeoffs: n 1+ o (1) space and log 2+ o (1) n query time, n log 2+ o (1) n space and n o (1) query time, n 4/3+ o (1) space and log 1+ o (1) n query time. We reduce a distance query to a variety of point location problems in additively weighted Voronoi diagrams and develop new algorithms for the point location problem itself using several partially persistent dynamic tree data structures.

It has been known since the early 1980s that Byzantine Agreement in the full information, asynchronous model is impossible to solve deterministically against even one crash fault [FLP 1985], but that it can be solved with probability 1 [Ben-Or 1983], even against an adversary that controls the scheduling of all messages and corrupts up to f

A k-vertex connectivity oracle for undirected G is a data structure that, given u,v∈ V(G), reports min{k,κ(u,v)}, where κ(u,v) is the pairwise vertex connectivity between u,v. There are three main measures of efficiency: construction time, query time, and space. Prior work of Izsak and Nutov [Inf. Process. Lett. 2012] shows that a data structure of total size O(knlogn), which can even be encoded as a O(klog3 n)-bit labeling scheme, can answer vertex-connectivity queries in O(klogn) time. The construction time is polynomial, but unspecified.

In the incremental cycle detection problem, edges are added to a directed graph (initially empty), and the algorithm has to report the presence of the first cycle, once it is formed. A closely related problem is the incremental topological sort problem, where edges are added to an acyclic graph, and the algorithm is required to maintain a valid topological ordering. Since these problems arise naturally in many applications such as scheduling tasks, pointer analysis, and circuit evaluation, they have been studied extensively in the last three decades. Motivated by the fact that in many of these applications, the presence of a cycle is not fatal, we study a generalization of these problems, incremental maintenance of strongly connected components (incremental SCC). Several incremental algorithms in the literature which do cycle detection and topological sort in directed acyclic graphs, such as those by [Michael A. Bender et al., 2016] and [Haeupler et al., 2012], also generalize to maintain strongly connected components and their topological sort in general directed graphs. The algorithms of [Haeupler et al., 2012] and [Michael A. Bender et al., 2016] have a total update time of O(m^{3/2}) and O(m⋅ min{m^{1/2},n^{2/3}}) respectively, and this is the state of the art for incremental SCC. But the most recent algorithms for incremental cycle detection and topological sort ([Bernstein and Chechik, 2018] and [Bhattacharya and Kulkarni, 2020]), which yield total (randomized) update time Õ(min{m^{4/3}, n²}), do not extend to incremental SCC. Thus, there is a gap between the best known algorithms for these two closely related problems. In this paper, we bridge this gap by extending the framework of [Bhattacharya and Kulkarni, 2020] to general directed graphs. More concretely, we give a Las Vegas algorithm for incremental SCCs with an expected total update time of Õ(m^{4/3}). A key ingredient in the algorithm of [Bhattacharya and Kulkarni, 2020] is a structural theorem (first introduced in [Bernstein and Chechik, 2018]) that bounds the number of "equivalent" vertices. Unfortunately, this theorem only applies to DAGs. We show a natural way to extend this structural theorem to general directed graphs, and along the way we develop a significantly simpler and more intuitive proof of this theorem.

Cardinality estimation is perhaps the simplest non-trivial statistical problem that can be solved via sketching. Industrially-deployed sketches like HyperLogLog, MinHash, and PCSA are mergeable, which means that large data sets can be sketched in a distributed environment, and then merged into a single sketch of the whole data set. In the last decade a variety of sketches have been developed that are non-mergeable, but attractive for other reasons. They are simpler, their cardinality estimates are strictly unbiased, and they have substantially lower variance. We evaluate sketching schemes on a reasonably level playing field, in terms of their memory-variance product (MVP). E.g., a sketch that occupies $5m$ bits and whose relative variance is $2/m$ (standard error $\sqrt{2/m}$) has an MVP of $10$. Our contributions are as follows. Cohen and Ting independently discovered what we call the Martingale transform for converting a mergeable sketch into a non-mergeable sketch. We present a simpler way to analyze the limiting MVP of Martingale-type sketches. We prove that the \Martingale{} transform is optimal in the non-mergeable world, and that \Martingale{} \fishmonger{} in particular is optimal among linearizable sketches, with an MVP of $H_0/2 \approx 1.63$. E.g., this is circumstantial evidence that to achieve 1\% standard error, we cannot do better than a 2 kilobyte sketch. \Martingale{} \fishmonger{} is neither simple nor practical. We develop a new mergeable sketch called \Curtain{} that strikes a nice balance between simplicity and efficiency, and prove that \Martingale{} \Curtain{} has limiting $\MVP\approx 2.31$. It can be updated with $O(1)$ memory accesses and it has lower empirical variance than \Martingale{} \LogLog, a practical non-mergeable version of HyperLogLog.

In this paper we continue a long line of work on representing the cut structure of graphs. We classify the types minimum vertex cuts, and the possible relationships between multiple minimum vertex cuts. As a consequence of these investigations, we exhibit a simple $O(κn)$-space data structure that can quickly answer pairwise $(κ+1)$-connectivity queries in a $κ$-connected graph. We also show how to compute the "closest" $κ$-cut to every vertex in near linear $\tilde{O}(m+poly(κ)n)$ time.

We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for such networks, as battery life is a crucial and limited resource. Working in a model where both sending and listening for messages deplete energy, we consider the problem of finding a maximal matching of the nodes in a radio network of arbitrary and unknown topology. We present a distributed randomized algorithm that produces, with high probability, a maximal matching. The maximum energy cost per node is O(log2 n), and the time complexity is O(Δ log(n)). Here n is any upper bound on the number of nodes, and Δ is any upper bound on the maximum degree; n and Δ are parameters of our algorithm that we assume are known a priori to all the processors. We note that there exist families of graphs for which our bounds on energy cost and time complexity are simultaneously optimal up to polylog factors, so any significant improvement would need additional assumptions about the network topology. We also consider the related problem of assigning, for each node in the network, a neighbor to back up its data in case of eventual node failure. Here, a key goal is to minimize the maximum load, defined as the number of nodes assigned to a single node. We present an efficient decentralized low-energy algorithm that finds a neighbor assignment whose maximum load is at most a polylog(n) factor bigger that the optimum.

In a recent breakthrough, Charalampopoulos, Gawrychowski, Mozes, and Weimann [9] showed that exact distance queries on planar graphs could be answered in no(1) time by a data structure occupying n1+o(1) space, i.e., up to o(1) terms, optimal exponents in time (0) and space (1) can be achieved simultaneously. Their distance query algorithm is recursive: it makes successive calls to a point-location algorithm for planar Voronoi diagrams, which involves many recursive distance queries. The depth of this recursion is non-constant and the branching factor logarithmic, leading to (log n)ω(1) = no(1) query times. In this paper we present a new way to do point-location in planar Voronoi diagrams, which leads to a new exact distance oracle. At the two extremes of our space-time tradeoff curve we can achieve either n1+o(1) space and log2+o(1) n query time, or n log2+o(1) n space and no(1) query time. All previous oracles with Õ(1) query time occupy space n1+Ω(1), and all previous oracles with space Õ(n) answer queries in nΩ(1) time.

Estimating the cardinality (number of distinct elements) of a large multiset is a classic problem in streaming and sketching, dating back to Flajolet and Martin’s classic Probabilistic Counting (PCSA) algorithm from 1983.

We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for such networks, as battery life is a crucial and limited resource. Working in a model where both sending and listening for messages deplete energy, we consider the problem of finding a maximal matching of the nodes in a radio network of arbitrary and unknown topology. We present a distributed randomized algorithm that produces, with high probability, a maximal matching. The maximum energy cost per node is $O(\log^2 n)$, where $n$ is the size of the network. The total latency of our algorithm is $O(n \log n)$ time steps. We observe that there exist families of network topologies for which both of these bounds are simultaneously optimal up to polylog factors, so any significant improvement will require additional assumptions about the network topology. We also consider the related problem of assigning, for each node in the network, a neighbor to back up its data in case of node failure. Here, a key goal is to minimize the maximum load, defined as the number of nodes assigned to a single node. We present a decentralized low-energy algorithm that finds a neighbor assignment whose maximum load is at most a polylog($n$) factor bigger that the optimum.

We present improved distributed algorithms for variants of the triangle finding problem in the model. We show that triangle detection, counting, and enumeration can be solved in rounds using expander decompositions . This matches the triangle enumeration lower bound of by Izumi and Le Gall [PODC’17] and Pandurangan, Robinson, and Scquizzato [SPAA’18], which holds even in the model. The previous upper bounds for triangle detection and enumeration in were and , respectively, due to Izumi and Le Gall [PODC’17]. An -expander decomposition of a graph is a clustering of the vertices such that (i) each cluster induces a subgraph with conductance at least and (ii) the number of inter-cluster edges is at most . We show that an -expander decomposition with can be constructed in rounds for any and positive integer . For example, a -expander decomposition only requires rounds to compute, which is optimal up to subpolynomial factors, and a -expander decomposition can be computed in rounds, for any arbitrarily small constant . Our triangle finding algorithms are based on the following generic framework using expander decompositions, which is of independent interest. We first construct an expander decomposition. For each cluster, we simulate algorithms with small overhead by applying the expander routing algorithm due to Ghaffari, Kuhn, and Su [PODC’17] Finally, we deal with inter-cluster edges using recursive calls.

In this paper we explore fundamental problems in randomized communication complexity such as computing SetIntersection on sets of size $k$ and EqualityTesting between vectors of length $k$. Sağlam and Tardos [ Proceedings of the 54 th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 678--687] and Brody et al. [ Algorithmica, 76 (2016), pp. 796--845] showed that for these types of problems, one can achieve optimal communication volume of $O(k)$ bits, with a randomized protocol that takes $O(\log^* k)$ rounds. They also proved that this is one point along the optimal round-communication trade-off curve. Aside from rounds and communication volume, there is a third parameter of interest, namely the error probability $p_{{err}}$, which we write $2^{-E}$. It is straightforward to show that protocols for SetIntersection or EqualityTesting need to send at least $\Omega(k + E)$ bits, regardless of the number of rounds. Is it possible to simultaneously achieve optimality in all three parameters, namely $O(k + E)$ communication and $O(\log^* k)$ rounds? In this paper we prove that there is no universally optimal algorithm, and we complement the existing round-communication trade-offs [M. Sağlam and G. Tardos, Proceedings of the 54 th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 678--687; J. Brody et al., Algorithmica, 76 (2016), pp. 796--845] with a new trade-off between rounds, communication, and probability of error. In particular, any protocol for solving multiple EqualityTesting in $r$ rounds with failure probability $p_{{err}} = 2^{-E}$ has communication volume $\Omega(Ek^{1/r})$. We present several algorithms for multiple EqualityTesting (and its variants) that match or nearly match our lower bound and the lower bound of [M. Sağlam and G. Tardos, Proceedings of the 54 th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 678--687; J. Brody et al., Algorithmica, 76 (2016), pp. 796--845]. Lower bounds on EqualityTesting extend to SetIntersection for every $r, k,$ and $p_{{err}}$ (which is trivial); in the reverse direction, we prove that upper bounds on EqualityTesting for $r, k, p_{{err}}$ imply similar upper bounds on SetIntersection with parameters $r+1, k,$ and $p_{{err}}$. Our original motivation for considering $p_{{err}}$ as an independent parameter came from the problem of enumerating triangles in distributed (${CONGEST}$) networks having maximum degree $\Delta$. We prove that this problem can be solved in $O(\Delta/\log n + \log\log \Delta)$ time with high probability $1-1/{poly}(n)$. This beats the trivial (deterministic) $O(\Delta)$-time algorithm and is superior to the $\tilde{O}(n^{1/3})$ algorithm of [Y. Chang, S. Pettie, and H. Zhang, Proceedings of the 30 th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 821--840; Y. Chang and T. Saranurak, Proceedings of the ACM Symposium on Principles of Distributed Computing, 2019, pp. 66--73] when $\Delta=\tilde{O}(n^{1/3})$.

We prove better lower bounds on additive spanners and emulators, which are lossy compression schemes for undirected graphs, as well as lower bounds on shortcut sets, which reduce the diameter of directed graphs. We prove that any $O(n)$-size shortcut set cannot bring the diameter below $\Omega(n^{1/6})$ and that any $O(m)$-size shortcut set cannot bring it below $\Omega(n^{1/11})$. These improve Hesse's [ Proceedings of the 14 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, MD, 2003] lower bound of $\Omega(n^{1/17})$. By combining these constructions with Abboud and Bodwin's [ J. ACM, 64 (2017), 28] edge-splitting technique, we get additive stretch lower bounds of $+\Omega(n^{1/11})$ for $O(n)$-size spanners and $+\Omega(n^{1/18})$ for $O(n)$-size emulators. These improve Abboud and Bodwin's $+\Omega(n^{1/22})$ lower bounds for both spanners and emulators.

We consider a model of energy complexity in Radio Networks in which transmitting or listening on the channel costs one unit of energy and computation is free. This simplified model captures key aspects of battery-powered sensors: that battery-life is most influenced by transceiver usage, and that at low transmission powers, the actual cost of transmitting and listening are very similar.

In this paper we explore fundamental problems in randomized communication complexity such as computing Set Intersection on sets of size k and Equality Testing between vectors of length k. Brody et al. [BCK+ 16] and Sağlam and Tardos [ST13] showed that for these types of problems, one can achieve optimal communication volume of O(k) bits, with a randomized protocol that takes O(log* k) rounds. They also proved [BCK+ 16, ST13] that this is one point along the optimal round-communication tradeoff curve. Aside from rounds and communication volume, there is a third parameter of interest, namely the error probability perr. It is straightforward to show that protocols for Set Intersection or Equality Testing need to send bits. Is it possible to simultaneously achieve optimality in all three parameters, namely communication and O(log* k) rounds? In this paper we prove that there is no universally optimal algorithm, and complement the existing round-communication trade-offs [BCK+ 16, ST13] with a new tradeoff between rounds, communication, and probability of error. In particular: Any protocol for solving Multiple Equality Testing in r rounds with failure probability perr = 2−E has communication volume Ω(Ek1/r). There exists a protocol for solving Multiple Equality Testing in r + log* (k/E) rounds with O(k + rEk1/r) communication, thereby essentially matching our lower bound and that of [BCK+ 16, ST13]. Lower bounds on Equality Testing extend to Set Intersection, for every r, k, and perr (which is trivial); in the reverse direction, upper bounds on Equality Testing for r, k, perr imply similar upper bounds on Set Intersection with parameters r + 1, k, and perr. Our original motivation for considering perr as an independent parameter came from the problem of enumerating triangles in distributed (CONGEST) networks having maximum degree Δ. We prove that this problem can be solved in O(Δ/log n + log log Δ) time with high probability 1 – 1/poly(n). This beats the trivial (deterministic) O(Δ)-time algorithm and is superior to the Õ(n1/3) algorithm of [CPZ19, CS19] when Δ = Õ(n1/3).

This paper focuses on the contention resolution problem on a shared communication channel that does not support collision detection. A shared communication channel is a multiple access channel, which consists of a sequence of synchronized time slots. Players on the channel may attempt to broadcast a packet (message) in any time slot. A player's broadcast succeeds if no other player broadcasts during that slot. If two or more players broadcast in the same time slot, then the broadcasts collide and both broadcasts fail. The lack of collision detection means that a player monitoring the channel cannot differentiate between the case of two or more players broadcasting in the same slot (a collision) and zero players broadcasting. In the contention-resolution problem, players arrive on the channel over time, and each player has one packet to transmit. The goal is to coordinate the players so that each player is able to successfully transmit its packet within reasonable time. However, the players can only communicate via the shared channel by choosing to either broadcast or not. A contention-resolution protocol is measured in terms of its throughput (channel utilization). Previous work on contention resolution that achieved constant throughput assumed that either players could detect collisions, or the players' arrival pattern is generated by a memoryless (non-adversarial) process.

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper, we present a new algorithm for $(\Delta+1)$-list coloring in the randomized ${LOCAL}$ model running in $O({Det}_{\scriptscriptstyle d}(\operatorname{poly} \log n))=O(\operatorname{poly}(\log\log n))$ time, where ${Det}_{\scriptscriptstyle d}(n')$ is the deterministic complexity of $(\deg+1)$-list coloring on $n'$-vertex graphs. (In this problem, each $v$ has a palette of size $\deg(v)+1$.) This improves upon a previous randomized algorithm of Harris, Schneider, and Su [ J. ACM, 65 (2018), 19] with complexity $O(\sqrt{\log \Delta} + \log\log n + {Det}_{\scriptscriptstyle d}(\operatorname{poly}\log n)) = O(\sqrt{\log n})$. Unless $\Delta$ is small, it is also faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski [ Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2016] and Barenboim, Elkin, and Goldenberg [ Proceedings of the 38th Annual ACM Symposium on Principles of Distributed Computing (PODC), 2018], with complexity $O(\sqrt{\Delta\log \Delta}\log^\ast \Delta + \log^* n)$. Our algorithm's running time is syntactically very similar to the $\Omega({Det}(\operatorname{poly}\log n))$ lower bound of Chang, Kopelowitz, and Pettie [ SIAM J. Comput., 48 (2019), pp. 122--143], where ${Det}(n')$ is the deterministic complexity of $(\Delta+1)$-list coloring on $n'$-vertex graphs. Although distributed coloring has been actively investigated for 30 years, the best deterministic algorithms for $(\deg+1)$- and $(\Delta+1)$-list coloring (that depend on $n'$ but not $\Delta$) use a black-box application of network decompositions. The recent deterministic network decomposition algorithm of Rozhoň and Ghaffari [ Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2020] implies that ${Det}_{\scriptscriptstyle d}(n')$ and ${Det}(n')$ are both $\operatorname{poly}(\log n')$. Whether they are asymptotically equal is an open problem.

We introduce new data structures for answering connectivity queries in graphs subject to batched vertex failures. A deterministic structure processes a batch of $d\leq d_\star$ failed vertices in $\tilde{O}(d^3)$ time and thereafter answers connectivity queries in $O(d)$ time. It occupies space $O(d_\star m\log n)$. We develop a randomized Monte Carlo version of our data structure with update time $\tilde{O}(d^2)$, query time $O(d)$, and space $\tilde{O}(m)$ for any failure bound $d\le n$. This is the first connectivity oracle for general graphs that can efficiently deal with an unbounded number of vertex failures. We also develop a more efficient Monte Carlo edge failure connectivity oracle. Using space $O(n\log^2 n)$, $d$ edge failures are processed in $O(d\log d\log\log n)$ time, and thereafter, connectivity queries are answered in $O(\log\log n)$ time, which are correct with high probability. Our data structures are based on a new decomposition theorem for an undirected graph $G=(V,E)$, which is of independent interest. It states that for any terminal set $U\subseteq V$ we can remove a set $B$ of $|U|/(s-2)$ vertices such that the remaining graph contains a Steiner forest for $U-B$ with maximum degree $s$.

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this article, we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows. Lower Bounds: First, we simplify the round elimination technique of Brandt et al. [16] and prove that (2Δ −2)-edge coloring requires Ω (log Δ log n ) time with high probability and Ω (log Δ n ) time deterministically, even on trees . Second, we show that a natural approach to computing (Δ +1)-edge colorings (Vizing’s theorem), namely, extending an arbitrary partial coloring by iteratively recoloring subgraphs, requires Ω (Δ log n ) time. Upper Bounds on General Graphs: We give a randomized edge coloring algorithm that can use palette sizes as small as Δ + Õ(√Δ), which is a natural barrier for randomized approaches. The running time of our (1+ϵ)Δ-edge coloring algorithm is usually dominated by O (\log ϵ −1 ) calls to a distributed Lovász local lemma (LLL) algorithm. For example, using the Chung-Pettie-Su LLL algorithm, we compute a (1+ϵ)Δ-edge coloring in O (log n ) time when ϵ ≥ (log 3 Δ) / √ Δ , or O (log Δ n ) + (log log n ) 3 + o (1) time when ϵ = Ω (1). When Δ is sublogarithmic in n the performance is improved with the Ghaffari-Harris-Kuhn LLL algorithm. Upper Bounds on Trees: We show that the Ω (log Δ log n ) lower bound can be nearly matched on trees. To establish this result, we develop a new distributed Lovász local lemma algorithm for tree-structured dependency graphs , which arise naturally from O (1)-round probabilistic algorithms run on trees. Specifically, our (1+ϵ)Δ-edge coloring algorithm for trees takes O (log (1 / ϵ)) ⋅ max { log log n \ log log log n , log log Δ log n } time when ϵ ≥ (log 3 Δ) / √ Δ, or O (max { log log n \ log log log n , log Δ log n }) time when ϵ = Ω (1).

We present improved distributed algorithms for triangle detection and its variants in the CONGEST model. We show that Triangle Detection, Counting, and Enumeration can be solved in Õ(n1/2) rounds. In contrast, the previous state-of-the-art bounds for Triangle Detection and Enumeration were Õ(n2/3) and Õ(n3/4), respectively, due to Izumi and LeGall (PODC 2017). The main technical novelty in this work is a distributed graph partitioning algorithm. We show that in Õ(n1–δ) rounds we can partition the edge set of the network G = (V, E) into three parts E = Em ∪ Es ∪ Er such that Each connected component induced by Em has minimum degree Ω(nδ) and conductance Ω(1/polylog(n)). As a consequence the mixing time of a random walk within the component is O(polylog(n)). The subgraph induced by Es has arboricity at most nδ. |Er| ≤ |E|/6. All of our algorithms are based on the following generic framework, which we believe is of interest beyond this work. Roughly, we deal with the set Es by an algorithm that is efficient for low-arboricity graphs, and deal with the set Er using recursive calls. For each connected component induced by Em, we are able to simulate CONGESTED-CLIQUE algorithms with small overhead by applying a routing algorithm due to Ghaffari, Kuhn, and Su (PODC 2017) for high conductance graphs.

Despite decades of research on AQP (approximate query processing), our understanding of sample-based joins has remained limited and, to some extent, even superficial. The common belief in the community is that joining random samples is futile. This belief is largely based on an early result showing that the join of two uniform samples is not an independent sample of the original join, and that it leads to quadratically fewer output tuples. Unfortunately, this early result has little applicability to the key questions practitioners face. For example, the success metric is often the final approximation's accuracy, rather than output cardinality. Moreover, there are many non-uniform sampling strategies that one can employ. Is sampling for joins still futile in all of these settings? If not, what is the best sampling strategy in each case? To the best of our knowledge, there is no formal study answering these questions. This paper aims to improve our understanding of sample-based joins and offer a guideline for practitioners building and using real-world AQP systems. We study limitations of offline samples in approximating join queries: given an offline sampling budget, how well can one approximate the join of two tables? We answer this question for two success metrics: output size and estimator variance. We show that maximizing output size is easy, while there is an information-theoretical lower bound on the lowest variance achievable by any sampling strategy. We then define a hybrid sampling scheme that captures all combinations of stratified, universe, and Bernoulli sampling, and show that this scheme with our optimal parameters achieves the theoretical lower bound within a constant factor. Since computing these optimal parameters requires shuffling statistics across the network, we also propose a decentralized variant in which each node acts autonomously using minimal statistics. We also empirically validate our findings on popular SQL and AQP engines.

Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish numerous connections between the deterministic and randomized complexities in the LOCAL model. Each of our results has a very compelling take-away message: Fast $\Delta$-coloring of trees requires random bits. Building on a recent randomized lower bound of Brandt et al. [ A lower bound for the distributed Lovász local lemma, in Proceedings of the 48th ACM Symposium on Theory of Computing (STOC), ACM, New York, 2016, pp. 479--488], we prove that the randomized complexity of $\Delta$-coloring a tree with maximum degree $\Delta$ is $O(\log_\Delta \log n + \log^\ast n)$ for any $\Delta \ge 55$, whereas its deterministic complexity is $\Omega(\log_\Delta n)$ for any $\Delta\ge 3$. This also establishes a large separation between the deterministic complexity of $\Delta$-coloring and $(\Delta+1)$-coloring trees. There is a gap in the deterministic complexity hierarchy. We show that any deterministic algorithm for a natural class of problems that runs in $O(1) + o(\log_\Delta n)$ rounds can be transformed to run in $O(\log^* n - \log^*\Delta + 1)$ rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires $\Omega(\log_\Delta n)$ time deterministically. This gives an alternate proof that deterministically $\Delta$-coloring a tree with small $\Delta$ takes $\Omega(\log_\Delta n)$ rounds. Graph shattering is necessary. We prove that the randomized complexity of any natural problem on instances of size $n$ is at least its deterministic complexity on instances of size $\sqrt{\log n}$. This shows that any randomized $O(1) + o(\log_\Delta \log n)$-round algorithm can be derandomized to run in deterministically $O(1) + o(\log_\Delta n)$ rounds and hence can be transformed to run in $O(\log^* n - \log^*\Delta + 1)$ rounds. This also shows that a deterministic $\Omega(\log_\Delta n)$ lower bound for any problem ($\Delta$-coloring a tree, for example) implies a randomized $\Omega(\log_\Delta \log n)$ lower bound. It illustrates that the graph shattering technique employed in recent randomized symmetry breaking algorithms is absolutely essential to the LOCAL model. For example, it is provably impossible to improve the $2^{O(\sqrt{\log\log n})}$ terms in the complexities of the best MIS and $(\Delta+1)$-coloring algorithms without also improving the $2^{O(\sqrt{\log n})}$-round Panconesi--Srinivasan algorithms.

The celebrated time hierarchy theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy--type theorem holds in the classic distributed $\mathsf{LOCAL}$ model has been open for many years. In particular, it is consistent with previous results that all natural problems in the $\mathsf{LOCAL}$ model can be classified according to a small constant number of complexities, such as $O(1),O(\log^* n), O(\log n), 2^{O(\sqrt{\log n})}$, etc. In this paper we establish the first time hierarchy theorem for the $\mathsf{LOCAL}$ model and prove that several gaps exist in the $\mathsf{LOCAL}$ time hierarchy. Our main results are as follows: (a) We define an infinite set of simple coloring problems called hierarchical $2\frac{1}{2}$-coloring. A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the $k$-level hierarchical $2\frac{1}{2}$-coloring problem is $\Theta(n^{1/k})$ for $k\in\mathbb{Z}^+$. The upper and lower bounds hold for both general graphs and trees and for both randomized and deterministic algorithms. (b) Consider any LCL problem on bounded degree trees. We prove an automatic speedup theorem that states that any randomized $n^{o(1)}$-time algorithm solving the LCL can be transformed into a deterministic $O(\log n)$-time algorithm. Together with a previous result [Y.-J. Chang, T. Kopelowitz, and S. Pettie, Proceedings of FOCS, 2016, pp. 615--624], this establishes that on trees, there are no natural deterministic complexities in the ranges $\omega(\log^* n)$---$o(\log n)$ or $\omega(\log n)$---$n^{o(1)}$. (c) We expose a new gap in the randomized time hierarchy on general graphs. Roughly speaking, any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in $O(T_{LLL})$ time: the complexity of the distributed Lovász local lemma (LLL) problem. In other words, the LLL is complete for sublogarithmic time. Finally, we revisit Naor and Stockmeyer's characterization of $O(1)$-time $\mathsf{LOCAL}$ algorithms for LCL problems (as order-invariant w.r.t. vertex IDs) and calculate the complexity gaps that are directly implied by their proof. For $n$-rings we see an $\omega(1)$---$o(\log^* n)$ complexity gap, for $(\sqrt{n}\times \sqrt{n})$-tori an $\omega(1)$---$o(\sqrt{\log^* n})$ gap, and for bounded degree trees and general graphs, an $\omega(1)$---$o(\log(\log^* n))$ complexity gap.

Energy is often the most constrained resource for battery-powered wireless devices, and most of the energy is often spent on transceiver usage (i.e., transmitting and receiving packets) rather than computation. In this article, we study the energy complexity of fundamental problems in several models of wireless radio networks. It turns out that energy complexity is very sensitive to whether the devices can generate random bits and their ability to detect collisions . We consider four collision detection models: Strong-CD (in which transmitters and listeners detect collisions), Sender-CD (in which only transmitters detect collisions), Receiver-CD (in which only listeners detect collisions), and No-CD (in which no one detects collisions). The take-away message of our results is quite surprising. For randomized algorithms, there is an exponential gap between the energy complexity of Sender-CD and Receiver-CD: Randomized: No-CD = Sender-CD > Receiver-CD = Strong-CD and for deterministic algorithms, there is another exponential gap in energy complexity, but in the reverse direction : Deterministic: No-CD = Receiver-CD > Sender-CD = Strong-CD Precisely, the randomized energy complexity of Leader Election is Θ(log * n ) in Sender-CD but Θ(log(log * n )) in Receiver-CD, where n is the number of devices, which is unknown to the devices at the beginning; the deterministic complexity of Leader Election is Θ(log N ) in Receiver-CD but Θ(log log N ) in Sender-CD, where N is the size of the ID space. There is a tradeoff between time and energy. We provide a new upper bound on the time-energy tradeoff curve for randomized algorithms. A critical component of this algorithm is a new deterministic Leader Election algorithm for dense instances, when n = Θ( N ), with inverse Ackermann energy complexity.

Cops and Robbers is a classic pursuit-evasion game played between a group of g cops and one robber on an undirected N-vertex graph G. We prove that the complexity of deciding the winner in the game under optimal play requires Omega (N^{g-o(1)}) time on instances with O(N log^2 N) edges, conditioned on the Strong Exponential Time Hypothesis. Moreover, the problem of calculating the minimum number of cops needed to win the game is 2^{Omega (sqrt{N})}, conditioned on the weaker Exponential Time Hypothesis. Our conditional lower bound comes very close to a conditional upper bound: if Meyniel's conjecture holds then the cop number can be decided in 2^{O(sqrt{N}log N)} time. In recent years, the Strong Exponential Time Hypothesis has been used to obtain many lower bounds on classic combinatorial problems, such as graph diameter, LCS, EDIT-DISTANCE, and REGEXP matching. To our knowledge, these are the first conditional (S)ETH-hard lower bounds on a strategic game.

We revisit multipass pairing heaps and path-balanced binary search trees (BSTs), two classical algorithms for data structure maintenance. The pairing heap is a simple and efficient "self-adjusting" heap, introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. In the multipass variant (one of the original pairing heap variants described by Fredman et al.) the minimum item is extracted via repeated pairing rounds in which neighboring siblings are linked. Path-balanced BSTs, proposed by Sleator (Subramanian, 1996), are a natural alternative to Splay trees (Sleator and Tarjan, 1983). In a path-balanced BST, whenever an item is accessed, the search path leading to that item is re-arranged into a balanced tree. Despite their simplicity, both algorithms turned out to be difficult to analyse. Fredman et al. showed that operations in multipass pairing heaps take amortized $O(\log{n} \cdot \log\log{n} / \log\log\log{n})$ time. For searching in path-balanced BSTs, Balasubramanian and Raman showed in 1995 the same amortized time bound of $O(\log{n} \cdot \log\log{n} / \log\log\log{n})$, using a different argument. In this paper we show an explicit connection between the two algorithms and improve the two bounds to $O\left(\log{n} \cdot 2^{\log^{\ast}{n}} \cdot \log^{\ast}{n}\right)$, respectively $O\left(\log{n} \cdot 2^{\log^{\ast}{n}} \cdot (\log^{\ast}{n})^2 \right)$, where $\log^{\ast}(\cdot)$ denotes the very slowly growing iterated logarithm function. These are the first improvements in more than three, resp. two decades, approaching in both cases the information-theoretic lower bound of $Ω(\log{n})$.

Energy is often the most constrained resource in networks of batterypowered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (transceiver usage) not computation. As an imperfect proxy for true energy usage, we define energy complexity to be the number of time slots a device transmits/listens; idle time and computation are free.

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this paper we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows. We simplify the round elimination technique of Brandt et al. [9] and prove that (2Δ – 2)-edge coloring requires Ω(logΔ log n) time w.h.p. and Ω(logΔ n) time deterministically, even on trees. The simplified technique is based on two ideas: the notion of an irregular running time (in which network components terminate the algorithm at prescribed, but irregular times) and some general observations that transform weak lower bounds into stronger ones. We give a randomized edge coloring algorithm that can use palette sizes as small as , which is a natural barrier for randomized approaches. The running time of the algorithm is at most O(log Δ · TLLL), where TLLL is the complexity of a permissive version of the constructive Lovász local lemma. We develop a new distributed Lovász local lemma algorithm for tree-structured dependency graphs, which leads to a (1 + ∊)Δ-edge coloring algorithm for trees running in O(log log n) time. This algorithm arises from two new results: a deterministic O(log n)-time LLL algorithm for tree-structured instances, and a randomized O(log log n)-time graph shattering method for breaking the dependency graph into independent O(log n)-size LLL instances. A natural approach to computing (Δ + 1)-edge colorings (Vizing's theorem) is to extend partial colorings by iteratively re-coloring parts of the graph, e.g., via “augmenting paths.” We prove that this approach may be viable, but in the worst case requires recoloring subgraphs of diameter Ω(Δ log n). This stands in contrast to distributed algorithms for Brooks’ theorem [32], which exploit the existence of O(logΔ n)-length augmenting paths.

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Δ+1)-list coloring in the randomized LOCAL model running in O(log∗n + Detd(poly logn)) time, where Detd(n′) is the deterministic complexity of (deg+1)-list coloring (v’s palette has size deg(v)+1) on n′-vertex graphs. This improves upon a previous randomized algorithm of Harris, Schneider, and Su (STOC 2016). with complexity O(√logΔ + loglogn + Detd(poly logn)), and (when Δ is sufficiently large) is much faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski (FOCS 2016), with complexity O(√Δlog2.5Δ + log* n).

The 3SUM problem is to decide, given a set of n real numbers, whether any three sum to zero. It is widely conjectured that a trivial O ( n 2 )-time algorithm is optimal on the Real RAM, and optimal even in the nonuniform linear decision tree model. Over the years the consequences of this conjecture have been revealed. This 3SUM conjecture implies Ω ( n 2 ) lower bounds on numerous problems in computational geometry, and a variant of the conjecture for integer inputs implies strong lower bounds on triangle enumeration, dynamic graph algorithms, and string matching data structures. In this article, we refute the conjecture that 3SUM requires Ω ( n 2 ) in the Real RAM and refute more forcefully the conjecture that its complexity is Ω ( n 2 ) in the linear decision tree model. In particular, we prove that the decision tree complexity of 3SUM is O ( n 3/2 √ log n ) and give two subquadratic 3SUM algorithms, a deterministic one running in O ( n 2 / (log n / log log n ) 2/3 ) time and a randomized one running in O ( n 2 (log log n ) 2 / log n ) time with high probability. Our results lead directly to improved bounds on the decision tree complexity of k -variate linear degeneracy testing for all odd k ≥ 3. Finally, we give a subcubic algorithm for a generalization of the (min ,+)-product over real-valued matrices and apply it to the problem of finding zero-weight triangles in edge-weighted graphs. We give a depth- O ( n 5/2 √ log n ) decision tree for this problem, as well as a deterministic algorithm running in time O ( n 3 (log log n ) 2 /log n ).

Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say $\tilde{O}(n^{1+\delta})$ bits. There is an inherent tradeoff between the sparsity parameter $\delta$ and the stretch function $f$ of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. It has been known for some time that when $\delta\ge 1/3$ there are schemes with constant additive stretch (distance $d$ is stretched to at most $f(d) = d + O(1)$), and recent results of Abboud and Bodwin show that when $\delta < 1/3$ there are no such schemes. Thus, to get practically efficient graph compression with $\delta \to 0$ we must pay superconstant additive stretch, but exactly how much do we have to pay? In this paper we show that the lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that characterize the asymptotic behavior of the optimal stretch function $f$ for sparsity parameter $\delta \in (0,1/3)$. Specifically, for any integer $k\ge 2$, any compression scheme using $O(n^{1+\frac{1}{2^k-1} - \epsilon})$ bits has a sublinear additive stretch function $f$: $f(d) = d + \Omega(d^{1-\frac{1}{k}})$. This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's $(1+\epsilon,\beta)$-spanners have an essentially optimal tradeoff between $\delta$, $\epsilon$, and $\beta$, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of $(1+\epsilon, O(k/\epsilon)^{k-1})$-spanners with size $O((k/\epsilon)^{h_k} kn^{1+\frac{1}{2^{k+1}-1}})$, where $h_k < 3/4$. This size bound improves on the spanners of Elkin and Peleg (2004), Thorup and Zwick (2006), and Pettie (2009). According to our lower bounds neither the size nor stretch function can be substantially improved. Our lower bound technique exhibits several interesting degrees of freedom in the framework of Abboud and Bodwin. By carefully exploiting these freedoms, we are able to obtain lower bounds for several related combinatorial objects. We get lower bounds on the size of $(\beta,\epsilon)$- hopsets, matching Elkin and Neiman's construction (2016), and lower bounds on shortcutting sets for digraphs that preserve the transitive closure. Our lower bound simplifies Hesse's (2003) refutation of Thorup's conjecture (1992), which stated that adding a linear number of shortcuts suffices to reduce the diameter to polylogarithmic. Finally, we show matching upper and lower bounds for graph compression schemes that work for graph metrics with girth at least $2\gamma+1$. One consequence is that Baswana et al.'s (2010) additive $O(\gamma)$-spanners with size $O(n^{1+\frac{1}{2\gamma+1}})$ cannot be improved in the exponent.

For decades, randomized exponential backoff has provided a critical algorithmic building block in situations where multiple devices seek access to a shared resource. Despite this history, the performance of standard exponential backoff is poor under worst-case scheduling of demands on the resource: (i) subconstant throughput can occur under plausible scenarios, and (ii) each of $N$ devices requires $\Omega(\log N)$ access attempts before obtaining the resource. In this paper, we address these shortcomings by offering a new backoff protocol for a shared communication channel that guarantees expected constant throughput with only $O(\log(\log^* N))$ channel accesses in expectation, even when packet arrivals are scheduled by an adversary. Central to this result are new algorithms for approximate counting and leader election with the same performance guarantees.

We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in O ( m √ n log( nN )) time, O ( m √ n ) per scale, which matches the running time of the best cardinality matching algorithms on sparse graphs [16, 20, 36, 37]. Here, m , n , and N bound the number of edges, vertices, and magnitude, respectively, of any integer edge weight. Our result improves on a 25-year-old algorithm of Gabow and Tarjan, which runs in O ( m √ n log n α ( m , n ) log( nN )) time.

The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem holds in the classic distributed LOCAL model has been open for many years. In particular, it is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as O(1), O(log* n), O(log n), 2^{O(sqrt{log n}), etc.In this paper we establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy. Our main results are as follows:• We define an infinite set of simple coloring problems called Hierarchical 2½-Coloring. A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the k-level Hierarchical 2½-Coloring problem is Θ(n^{1/k}), for positive integer k. The upper and lower bounds hold for both general graphs and trees, and for both randomized and deterministic algorithms.• Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem that states that any randomized n^{o(1)}-time algorithm solving the LCL can be transformed into a deterministic O(log n)-time algorithm. Together with a previous result, this establishes that on trees, there are no natural deterministic complexities in the ranges ω(log* n)—o(log n) or ω(log n)—n^{o(1)}.• We expose a gap in the randomized time hierarchy on general graphs. Roughly speaking, any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in O(T_{LLL}) time, which is the complexity of the distributed Lovasz local lemma problem, currently known to be Ω(log log n) and 2^{O(sqrt{log log n})} on bounded degree graphs.Finally, we revisit Naor and Stockmeyers characterization of O(1)-time LOCAL algorithms for LCL problems (as order-invariant w.r.t. vertex IDs) and calculate the complexity gaps that are directly implied by their proof. For n-rings we see a ω(1)—o(log* n) complexity gap, for (sqrt{n} × √{n})-tori an ω(1)—o(sqrt{log* n}) gap, and for bounded degree trees and general graphs, an ω(1)—o(log(log* n)) complexity gap.

This paper investigates the task of load balancing where the objective function is to minimize the p-norm of loads, for p\geq 1, in both static and incremental settings. We consider two closely related load balancing problems. In the bipartite matching problem we are given a bipartite graph G=(C\cup S, E) and the goal is to assign each client c\in C to a server s\in S so that the p-norm of assignment loads on S is minimized. In the graph orientation problem the goal is to orient (direct) the edges of a given undirected graph while minimizing the p-norm of the out-degrees. The graph orientation problem is a special case of the bipartite matching problem, but less complex, which leads to simpler algorithms. For the graph orientation problem we show that the celebrated Chiba-Nishizeki peeling algorithm provides a simple linear time load balancing scheme whose output is an orientation that is 2-competitive, in a p-norm sense, for all p\geq 1. For the bipartite matching problem we first provide an offline algorithm that computes an optimal assignment. We then extend this solution to the online bipartite matching problem with reassignments, where vertices from C arrive in an online fashion together with their corresponding edges, and we are allowed to reassign an amortized O(1) vertices from C each time a new vertex arrives. In this online scenario we show how to maintain a single assignment that is 8-competitive, in a p-norm sense, for all p\geq 1.

Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say Õ(n1+δ) bits. There is an inherent tradeoff between the sparsity parameter δ and the stretch function f of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. It has been known for some time that when δ > 1/3 there are schemes with constant additive stretch (distance d is stretched to at most f (d) = d + O(1)), and recent results of Abboud and Bodwin show that when δ < 1/3 there are no such schemes. Thus, to get practically efficient graph compression with δ → 0 we must pay super-constant additive stretch, but exactly how much do we have to pay? In this paper we show that the lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that characterize the asymptotic behavior of the optimal stretch function f for sparsity parameter δ ∊ (0,1/3). Specifically, for any integer k ≥ 2, any compression scheme with size has a sublinear additive stretch function f: This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's (1 + ∊, ß)-spanners have an essentially optimal tradeoff between δ, ∊, and β, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of (1 + ∊, O(k/ ∊)k—1)-spanners with size where hk < 3/4. This size bound improves on the spanners of Elkin and Peleg (2004), Thorup and Zwick (2006), and Pet- tie (2009). According to our lower bounds neither the size nor stretch function can be substantially improved. Our lower bound technique exhibits several interesting degrees of freedom in the framework of Abboud and Bodwin. By carefully exploiting these freedoms, we are able to obtain lower bounds for several related combinatorial objects. We get lower bounds on the size of (β, ∊)-hopsets, matching Elkin and Neiman's construction (2016), and lower bounds on shortcut- ting sets for digraphs that preserve the transitive closure. Our lower bound simplifies Hesse's (2003) refutation of Thorup's conjecture (1992), which stated that adding a linear number of shortcuts suffices to reduce the diameter to polylogarithmic. Finally, we show matching upper and lower bounds for graph compression schemes that work for graph metrics with girth at least 2γ + 1. One consequence is that Baswana et al.'s (2010) additive O(7)-spanners with size cannot be improved in the exponent.

We introduce new data structures for answering connectivity queries in graphs subject to batched vertex failures. Our deterministic structure processes a batch of d ≤ d* failed vertices in Õ(d3) time and thereafter answers connectivity queries in Õ(d) time. It occupies space Õ(d*m log n). We develop a randomized Monte Carlo version of our data structure with update time Õ(d2), query time Õ(d), and space Õ(m) for any d*. This is the first connectivity oracle for general graphs that can efficiently deal with an unbounded number of vertex failures. Our data structures are based on a new decomposition theorem for an undirected graph G = (V, E), which is of independent interest. It states that for any terminal set U ⊆ V we can remove a set B of |U|/(s — 2) vertices such that the remaining graph contains a Steiner forest for U - B with maximum degree s.

We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in time, per scale, which matches the running time of the best cardinality matching algorithms on sparse graphs [29, 18]. Here m,n, and n bound the number of edges, vertices, and magnitude of any integer edge weight. Our result improves on a 25-year old algorithm of Gabow and Tarjan, which runs in time.

Computing the strongly connected Components (SCCs) in a graph $G=(V,E)$ is known to take only $O(m + n)$ time using an algorithm by Tarjan [SIAM J. Comput., 1 (1972), pp. 146--160] where $m = |E|$, $n=|V|$. For fully dynamic graphs, conditional lower bounds provide evidence that the update time cannot be improved by polynomial factors over recomputing the SCCs from scratch after every update. Nevertheless, substantial progress has been made to find algorithms with fast update time for decremental graphs, i.e., graphs that undergo edge deletions. In this paper, we present the first algorithm for general decremental graphs that maintains the SCCs in total update time $\tilde{O}(m)$, thus only a polylogarithmic factor from the optimal running time. (We use $\tilde{O}(f(n))$ notation to suppress logarithmic factors, i.e., $g(n) = \tilde{O}(f(n))$ if $g(n) = O(f(n) {polylog}(n)).$) Our result also yields the fastest algorithm for the decremental single-source reachability (SSR) problem which can be reduced to decrementally maintaining SCCs. Using a well-known reduction, we use our decremental result to achieve new update/query-time trade-offs in the fully dynamic setting. We can maintain the reachability of pairs $S \times V$, $S \subseteq V$ in fully dynamic graphs with update time $\tilde{O}(\frac{|S|m}{t})$ and query time $O(t)$ for all $t \in [1,|S|]$; this matches to polylogarithmic factors the best all-pairs reachability algorithm for $S = V$.

Energy is often the most constrained resource for battery-powered wireless devices and the lion's share of energy is often spent on transceiver usage (sending/receiving packets), not on computation. In this paper we study the energy complexity of Leader Election and Approximate Counting in several models of wireless radio networks. It turns out that energy complexity is very sensitive to whether the devices can generate random bits and their ability to detect collisions. We consider four collision-detection models: Strong-CD (in which transmitters and listeners detect collisions), Sender-CD and Receiver-CD (in which only transmitters or only listeners detect collisions), and No-CD (in which no one detects collisions.)

We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time O(sqrt{(n(log(log(n)))^2)/log(n)}) and constant query time. This improves on the previous best deterministic worst case algorithm of Frederickson (SIAM J. Comput., 1985) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM, 1997), which had update time O(sqrt{n}). All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees.

Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. We prove that these exponential gaps are necessary and establish numerous connections between the deterministic and randomized complexities in the LOCAL model. Each of our results has a very compelling take-away message: 1) Building on the recent randomized lower bounds of Brandt et al. [1], we prove that the randomized complexity of Δ-coloring a tree with maximum degree Δ is O(log Δ log n + log*n), for any Δ > = 55, whereas its deterministic complexity is Ω(log Δ n) for any Δ > = 3. This also establishes a large separation between the deterministic complexity of Δ-coloring and (Δ+1)-coloring trees. 2) We prove that any deterministic algorithm for a natural class of problems that runs in O(1) + o(log Δ n) rounds can be transformed to run in O(log*n - log*Δ + 1) rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires Ω(log Δ n) time deterministically. This gives an alternate proof that deterministically Δ-coloring a tree with small Δ takes Ω(log Δ n) rounds. 3) We prove that the randomized complexity of any natural problem on instances of size n is at least its deterministic complexity on instances of size √log n. This shows that a deterministic Ω(log Δ n) lower bound for any problem (Δ-coloring a tree, for example) implies a randomized Ω(log Δ log n) lower bound. It also illustrates that the graph shattering technique employed in recent randomized symmetry breaking algorithms is absolutely essential to the LOCAL model. For example, it is provably impossible to improve the 2O(√log log n) term in the complexities of the best MIS and (Δ+1)-coloring algorithms without also improving the 2O(√log n)-round Panconesi-Srinivasan algorithm.

We examine the complexity of the online Dictionary Matching with One Gap Problem (DMOG) which is the following. Preprocess a dictionary D of d patterns, where each pattern contains a special gap symbol that can match any string, so that given a text that arrives online, a character at a time, we can report all of the patterns from D that are suffixes of the text that has arrived so far, before the next character arrives. In more general versions the gap symbols are associated with bounds determining the possible lengths of matching strings. Online DMOG captures the difficulty in a bottleneck procedure for cyber-security, as many digital signatures of viruses manifest themselves as patterns with a single gap. In this paper, we demonstrate that the difficulty in obtaining efficient solutions for the DMOG problem, even in the offline setting, can be traced back to the infamous 3SUM conjecture. We show a conditional lower bound of Omega(delta(G_D)+op) time per text character, where G_D is a bipartite graph that captures the structure of D, delta(G_D) is the degeneracy of this graph, and op is the output size. Moreover, we show a conditional lower bound in terms of the magnitude of gaps for the bounded case, thereby showing that some known offline upper bounds are essentially optimal. We also provide matching upper-bounds (up to sub-polynomial factors), in terms of the degeneracy, for the online DMOG problem. In particular, we introduce algorithms whose time cost depends linearly on delta(G_D). Our algorithms make use of graph orientations, together with some additional techniques. These algorithms are of practical interest since although delta(G_D) can be as large as sqrt(d), and even larger if G_D is a multi-graph, it is typically a very small constant in practice. Finally, when delta(G_D) is large we are able to obtain even more efficient solutions.

Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish numerous connections between the deterministic and randomized complexities in the LOCAL model. Each of our results has a very compelling take-away message:

The 3SUM conjecture has proven to be a valuable tool for proving conditional lower bounds on dynamic data structures and graph problems. This line of work was initiated by Pâtraşcu (STOC 2010) who reduced 3SUM to an offline SetDisjointness problem. However, the reduction introduced by Pâtraşcu suffers from several inefficiencies, making it difficult to obtain tight conditional lower bounds from the 3SUM conjecture. In this paper we address many of the deficiencies of Pâtraşcu's framework. We give new and efficient reductions from 3SUM to offline SetDisjointness and offline SetIntersection (the reporting version of SetDisjointness) which leads to polynomially higher lower bounds on several problems. Using our reductions, we are able to show the essential optimality of several algorithms, assuming the 3SUM conjecture. Chiba and Nishizeki's O(mα)-time algorithm (SICOMP 1985) for enumerating all triangles in a graph with arboricity/degeneracy α is essentially optimal, for any α. Bjørklund, Pagh, Williams, and Zwick's algorithm (ICALP 2014) for listing t triangles is essentially optimal (assuming the matrix multiplication exponent is ω = 2). Any static data structure for SetDisjointness that answers queries in constant time must spend Ω(N2–o(1)) time in preprocessing, where N is the size of the set system. These statements were unattainable via Pâtraşcu's reductions. We also introduce several new reductions from 3SUM to pattern matching problems and dynamic graph problems. Of particular interest are new conditional lower bounds for dynamic versions of Maximum Cardinality Matching, which introduce a new technique for obtaining amortized lower bounds.

For decades, randomized exponential backoff has provided a critical algorithmic building block in situations where multiple devices seek access to a shared resource. Surprisingly, despite this history, the performance of standard backoff is poor under worst-case scheduling of demands on the resource: (i) subconstant throughput can occur under plausible scenarios, and (ii) each of N devices requires Omega(log N) access attempts before obtaining the resource.

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 article 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 the following: —An MIS algorithm running in O (log 2 Δ + 2 o (√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 ≪ Δ ≪ 2√log n , and comes close to the Ω(log Δ / log 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 nearly optimal . —A (Δ + 1)-coloring algorithm requiring O (log Δ + 2 o (√log log n ) time, improving on an O (log Δ + √log n )-time algorithm of Schneider and Wattenhofer. —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 (√log n )-time maximal matching algorithm for graphs with arboricity up to 2√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.

Thorup and Zwick [2001a] proposed a landmark distance oracle with the following properties. Given an n -vertex undirected graph G = ( V , E ) and a parameter k = 1, 2, …, their oracle has size O ( kn 1 + 1/ k ), and upon a query ( u , v ) it constructs a path Π between u and v of length δ( u , v ) such that d G ( u , v ) ⩽ δ( u , v ) ⩽ (2 k − 1) d G ( u , v ). The query time of the oracle from Thorup and Zwick [2001a] is O ( k ) (in addition to the length of the returned path), and it was subsequently improved to O (1) [Wulff-Nilsen 2012; Chechik 2014]. A major drawback of the oracle of Thorup and Zwick [2001a] is that its space is Ω( n · log n ). Mendel and Naor [2006] 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 article, 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 constant ϵ > 0. In particular, for k = log n , our oracle provides logarithmic stretch using linear size. Another variant of our oracle has size O ( n loglog n ), polylogarithmic stretch, and query time O (loglog n ). For unweighted graphs, we devise a distance oracle with multiplicative stretch O (1), additive stretch O (β( k )), for a function β(·), space O ( n 1 + 1/ k ), and query time O ( n ϵ ), for an arbitrarily small constant ϵ > 0. The tradeoff between multiplicative stretch and size in these oracles is far below Erdős’s girth conjecture threshold (which is stretch 2 k − 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 [2001]. 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. We believe that this oracle is of independent interest.

In a seminal paper [27] for any n-vertex undirected graph G = (V,E) and a parameter k = 1, 2, …, Thorup and Zwick constructed a distance oracle of size O(kn1+1/k) which upon a query (u, v) constructs a path Π between u and ν of length δ(u, v) such that dG(u,ν) ≤ δ(u,v) ≤ (2k–1)dG(u,v). The query time of the oracle from [27] is O(k) (in addition to the length of the returned path), and it was subsequently improved to O(1) [29, 11]. A major drawback of the oracle of [27] is that its space is Ω(n · log n). Mendel and Naor [18] devised an oracle with space O(n1+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(n1+1/k), stretch O(k) and query time O(nε), for an arbitrarily small ε > 0. In particular, for k = log n our oracle provides logarithmic stretch using linear size. Another variant of our oracle has linear size, 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 β, space O(n1+1/k · β), and query time O(nε), for an arbitrarily small constant ε > 0. The tradeoff between multiplicative stretch and size in these oracles is far below Erdös's 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(n1+1/k). A similar type of tradeoff was exhibited by a construction of (1 + ε, β)-spanners due to Elkin and Peleg [16]. 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. We believe that this oracle is of independent interest.

Graph coloring is a central problem in distributed computing. Both vertex- and edge-coloring problems have been extensively studied in this context. In this paper we show that a (2Δ — l)-edge-coloring can be computed in time smaller than logε n for any ε > 0, specifically, in rounds. This establishes a separation between the (2Δ — 1)-edge-coloring and Maximal Matching problems, as the latter is known to require time [15]. No such separation is currently known between the (Δ + l)-vertex-coloring and Maximal Independent Set problems. We devise a (1 + ε)Δ-edge-coloring algorithm for an arbitrarily small constant ε > 0. This result applies whenever Δ ≥ Δε, for some constant Δε which depends on e. The running time of this algorithm is . A much earlier logarithmic-time algorithm by Dubhashi, Grable and Panconesi [11] assumed Δ ≥ (log n)1+Ω(1). For Δ = (log n)1+Ω(1) the running time of our algorithm is only O (log* n). This constitutes a drastic improvement of the previous logarithmic bound [11, 9]. Our results for (2Δ — 1)-edge-coloring also follows from our more general results concerning (1 — ε)-locally sparse graphs. Specifically, we devise a (Δ + l)-vertex coloring algorithm for (1 — ε)-locally sparse graphs that runs in O(log* Δ + log(l/ε)) rounds for any ε > 0, provided that ε Δ = (log n)1+Ω(1). We conclude that the (Δ + l)-vertex coloring problem for (1 — ε)-locally sparse graphs can be solved in time. This imply our result about (2Δ — 1)-edge-coloring, because (2Δ — 1)-edge-coloring reduces to (Δ + l)-vertex-coloring of the line graph of the original graph, and because line graphs are (1/2 + o(1))-locally sparse.

An (r, s)-formation is the concatenation of s permutations over an r-letter alphabet. Formation-free sequences are a generalization of standard Davenport-Schinzel sequences (where r = 2) and can be used to obtain good bounds on the extremal function of any forbidden subsequence. More recently formation-free sequences have been applied to bounding the size of sets of permutations with fixed VC-dimension.

We present distributed network algorithms to compute weighted and unweighted matchings with improved approximation ratios and running times. The computational model is a network of processors exchanging O (log n )-bit messages (the CONGEST model). For unweighted graphs, we give an algorithm providing (1-ϵ)-approximation in O (log n ) time for any constant ϵ>0, improving on the classical ½-approximation in O log n ) time of Israeli and Itai [1986]. The time complexity of the algorithm depends on 1⁃ϵ exponentially in the general case, and polynomially in bipartite graphs. For weighted graphs, we present another algorithm which provides (½-ϵ) approximation in general graphs in O (logϵ -1 log n ) time, improving on the previously known algorithms which attain (¼-ϵ)-approximation in O (log n ) time or ½-approximation in O ( n ) time. All our algorithms are randomized: the complexity bounds hold both with high probability and for the expected running time.

One of the longest-standing open problems in computational geometry is bounding the complexity of the lower envelope of n univariate functions, each pair of which crosses at most s times, for some fixed s . This problem is known to be equivalent to bounding the length of an order- s Davenport-Schinzel sequence, namely, a sequence over an n -letter alphabet that avoids alternating subsequences of the form a … b … a … b … with length s +2. These sequences were introduced by Davenport and Schinzel in 1965 to model a certain problem in differential equations and have since been applied to bound the running times of geometric algorithms, data structures, and the combinatorial complexity of geometric arrangements. Let λ s ( n ) be the maximum length of an order- s DS sequence over n letters. What is λ s asymptotically? This question has been answered satisfactorily [Hart and Sharir 1986; Agarwal et al. 1989; Klazar 1999; Nivasch 2010], when s is even or s ≤ 3. However, since the work of Agarwal et al. in the mid-1980s, there has been a persistent gap in our understanding of the odd orders. In this work, we effectively close the problem by establishing sharp bounds on Davenport-Schinzel sequences of every order s . Our results reveal that, contrary to one's intuition, λ s ( n ) behaves essentially like λ s -1 ( n ) when s is odd. This refutes conjectures by Alon et al. [2008] and Nivasch [2010].

We present new, and mostly sharp, bounds on the maximum length of certain generalizations of Davenport--Schinzel (DS) sequences. Among the results are sharp bounds on order-$s$ double DS sequences, for all $s$, sharp bounds on (double) formation-free sequences, and new lower bounds on sequences avoiding zig-zagging patterns.

The 3SUM problem is to decide, given a set of n real numbers, whether any three sum to zero. It is widely conjectured that a trivial O(n2)-time algorithm is optimal and over the years the consequences of this conjecture have been revealed. This 3SUM conjecture implies Ω(n2) lower bounds on numerous problems in computational geometry and a variant of the conjecture implies strong lower bounds on triangle enumeration, dynamic graph algorithms, and string matching data structures. In this paper we refute the 3SUM conjecture. We prove that the decision tree complexity of 3SUM is O(n3/2√/log n) and give two subquadratic 3SUM algorithms, a deterministic one running in O(n2/(log n/ log log n)2/3) time and a randomized one running in O(n2(log log n)2/ log n) time with high probability. Our results lead directly to improved bounds for k-variate linear degeneracy testing for all odd k ≥ 3. The problem is to decide, given a linear function f(x1, ... , xk) = α0+ Σ1≤1≤kαixiand a set A ⊂ ℝ, whether 0 ∈ f(Ak). We show the decision tree complexity of this problem is O(nk/2√log n). Finally, we give a subcubic algorithm for a generalization of the (min, +)-product over real-valued matrices and apply it to the problem of finding zero-weight triangles in weighted graphs. We give a depth-O(n5/2√log n) decision tree for this problem, as well as an algorithm running in time O(n3(log log n)2/ log n).

The Lovasz Local Lemma (LLL), introduced by Erdos and Lovasz in 1975, is a powerful tool of the probabilistic method that allows one to prove that a set of n "bad" events do not happen with non-zero probability, provided that the events have limited dependence. However, the LLL itself does not suggest how to find a point avoiding all bad events. Since the work of Beck (1991) there has been a sustained effort to find a constructive proof (i.e. an algorithm) for the LLL or weaker versions of it. In a major breakthrough Moser and Tardos (2010) showed that a point avoiding all bad events can be found efficiently. They also proposed a distributed/parallel version of their algorithm that requires O(log2 n) rounds of communication in a distributed network.

We consider the problem of broadcasting a message from a sender to n ≥ 1 receivers in a time-slotted, single-hop, wireless network with a single communication channel. Sending and listening dominate the energy usage of small wireless devices and this is abstracted as a unit cost per time slot. A jamming adversary exists who can disrupt the channel at unit cost per time slot, and aims to prevent the transmission of the message. Let T be the number of slots jammed by the adversary. Our goal is to design algorithms whose cost is resource-competitive, that is, whose per-device cost is a function, preferably o(T), of the adversary's cost. Devices must work with limited knowledge. The values n, T, and the adversary's jamming strategy are unknown.

The maximum cardinality and maximum weight matching problems can be solved in Õ ( m √ n ) time, a bound that has resisted improvement despite decades of research. (Here m and n are the number of edges and vertices.) In this article, we demonstrate that this “ m √ n barrier” can be bypassed by approximation. For any ε > 0, we give an algorithm that computes a (1 − ε )-approximate maximum weight matching in O ( mε −1 log ε −1 ) time, that is, optimal linear time for any fixed ε . Our algorithm is dramatically simpler than the best exact maximum weight matching algorithms on general graphs and should be appealing in all applications that can tolerate a negligible relative error.

One of the oldest unresolved problems in extremal combinatorics is to determine the maximum length of Davenport-Schinzel sequences, where an order-s DS sequence is defined to be one over an n-letter alphabet that avoids alternating subsequences of the form a ··· b ··· a ··· b ··· with length s+2. These sequences were introduced by Davenport and Schinzel in 1965 to model a certain problem in differential equations and have since become an indispensable tool in computational geometry and the analysis of discrete geometric structures.

We present new bounds on the locality of several classical symmetry breaking tasks in distributed networks. A sampling of the results include 1) A randomized algorithm for computing a maximal matching (MM) in O(log Δ + (log log n)4) rounds, where Δ is the maximum degree. This improves a 25-year old randomized algorithm of Israeli and Itai that takes O(log n) rounds and is provably optimal for all log Δ in the range [(log log n)4, √log n]. 2) A randomized maximal independent set (MIS) algorithm requiring O(log Δ√log n) rounds, for all Δ, and only 2O(√log log n) rounds when Δ = poly(log n). These improve on the 25-year old O(log n)-round randomized MIS algorithms of Luby and Alon, Babai, and Itai when log Δ ≫ √log n. 3) A randomized (Δ + 1)-coloring algorithm requiring O(log Δ + 2O((√log log n)) rounds, improving on an algorithm of Schneider and Wattenhofer that takes O(log Δ + √log n) rounds. This result implies that an O(Δ)-coloring can be computed in 2O(√log log n)rounds for all Δ, improving on Kothapalli et al.'s O(√log n)-round algorithm. We also introduce a new technique for reducing symmetry breaking problems on low arboricity graphs to low degree graphs. Corollaries of this reduction include MM and MIS algorithms for low arboricity graphs (e.g., planar graphs and graphs that exclude any fixed minor) requiring O(√log n) and O(log2/3n) rounds w.h.p., respectively.

This section of SIAM Journal on Computing contains extended versions of selected papers from the 43rd ACM Symposium on Theory of Computing (STOC), held June 6--8, 2011, in San Jose, California, as part of the fifth Federated Computing Research Conference (FCRC). The STOC proceedings contained 84 papers, which were selected from 304 submissions by the program committee, consisting of Ittai Abraham, Alexandr Andoni, Avrim Blum, Allan Borodin, Kousha Etessami, Lisa Fleischer, Venkatesan Guruswami, David Kempe, Frederic Magniez, Dieter van Melkebeek, Daniele Micciancio, Moni Naor, Kobbi Nissim, Seth Pettie, Ronitt Rubinfeld, Amir Shpilka, Ravi Sundaram, Eva Tardos, Prasad Tetali, Salil Vadhan (chair), Kasturi Varadarajan, Nisheeth Vishnoi, John Watrous, and Ryan Williams. Five of the STOC papers appear in this special section, each one expanded and fully refereed according to the high standards of the journal. They cover a diverse collection of topics: In “Distributed Verification and Hardness of Distributed Approximation,” Das Sarma, Holzer, Kor, Korman, Nanongkai, Pandurangan, Peleg, and Wattenhofer prove strong lower bounds on the power of distributed networks to verify their own properties (such as connectivity) and solve optimization problems such as computing approximate shortest paths or approximate min-cuts. They establish new connections between distributed computation and two-party communication complexity. The paper “Pareto Optimal Solutions for Smoothed Analysts” by Moitra and O'Donnell considers the smoothed complexity of discrete multi-objective optimization problems with $d+1$ linear objectives and with a solution space consisting of binary $n$-vectors. The authors show that, in a suitable smoothed analysis framework for such problems, the expected number of Pareto optimal solutions is at most $n^{2d}$. This improves greatly, as a function of the dimension d, an earlier upper bound established by Roeglin and Teng, which had roughly the form $n^{d^d}$. The paper “Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter” by Saxena and Seshadhri provides the first deterministic polynomial-time identity test for depth-3 arithmetic circuits with bounded top-fanin that only needs blackbox access to the circuit. Their construction has the feature that it works for arbitrary fields. In their paper “An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance,” Chakrabarti and Regev prove a lower bound establishing that the randomized communication complexity of the gap-Hamming-distance problem is linear. In obtaining this result, they have resolved an important and well-studied communication complexity problem having a fundamental connection to the data stream model of computation. Svensson's paper “Santa Claus Schedules Jobs on Unrelated Machines” breaks the barrier of 2 for efficiently approximating the minimum makespan for scheduling jobs on unrelated machines in the setting where all machines on which a given job can run take the same amount of time for that job. We thank the authors, the referees, and the full program committee for all their work, which made this special section possible.

Forbidden substructure theorems have proved to be among of the most versatile tools in bounding the complexity of geometric objects and the running time of geometric algorithms. To apply them one typically transcribes an algorithm execution or geometric object as a sequence over some alphabet or a 0-1 matrix, proves that this object avoids some subsequence or submatrix σ, then uses an off the shelf bound on the maximum size of such a σ-free object. As a historical trend, expanding our library of forbidden substructure theorems has led to better bounds and simpler analyses of the complexity of geometric objects. We establish new and tight bounds on the maximum length of generalized Davenport-Schinzel sequences, which are those whose subsequences are not isomorphic to some fixed sequence σ. (The standard Davenport-Schinzel sequences restrict σ to be of the form abab · · ·.) 1. We prove that N-shaped forbidden subsequences (of the form abc · · · xyzyx · · · cbabc · · · xyz) have a linear extremal function. Our proof dramatically improves an earlier one of Klazar and Valtr in the leading constants and overall simplicity. This result tightens the (astronomical) leading constants in Valtr’s O(n log n) bound on geometric graphs without k = O(1) mutually crossing edges. 2. We prove tight Θ(nα(n)) bounds on sequences avoiding both ababab and all M-shaped sequences of the form ab · · · yzzy · · · baab · · · yzzy · · · ba. A consequence of this result is that the complexity of the union of n δ-fat triangles is O(n log ∗ nα(n)), which improves, slightly, a recent bound of Ezra, Aronov, and Sharir. Here α is the inverse-Ackermann function. 3. We give a complete characterization of 3-letter linear

A generalized Davenport–Schinzel sequence is one over a finite alphabet that excludes subsequences isomorphic to a fixed forbidden subsequence. The fundamental problem in this area is bounding the maximum length of such sequences. Following Klazar, we let $\mathrm{Ex}(\sigma,n)$ be the maximum length of a sequence over an n-letter alphabet excluding subsequences isomorphic to $\sigma$. It has been proved that for every $\sigma$, $\mathrm{Ex}(\sigma,n)$ is either linear or very close to linear. In particular it is $O(n2^{\alpha(n)^{O(1)}})$, where $\alpha$ is the inverse-Ackermann function and $O(1)$ depends on $\sigma$. In much the same way that the complete graphs $K_5$ and $K_{3,3}$ represent the minimal causes of nonplanarity, there must exist a set $\Phi_{Nonlin}$ of minimal nonlinear forbidden subsequences. Very little is known about the size or membership of $\Phi_{Nonlin}$. In this paper we construct an infinite antichain of nonlinear forbidden subsequences which, we argue, strongly supports the conjecture that $\Phi_{Nonlin}$ is itself infinite. Perhaps the most novel contribution of this paper is a succinct, humanly readable code for expressing the structure of forbidden subsequences.

Given a weighted graph, the maximum weight matching problem (MWM) is to find a set of vertex-disjoint edges with maximum weight. In the 1960s Edmonds showed that MWMs can be found in polynomial time. At present the fastest MWM algorithm, due to Gabow and Tarjan, runs in Õ(m√n) time, where m and n are the number of edges and vertices in the graph. Surprisingly, restricted versions of the problem, such as computing (1 - ϵ)-approximate MWMs or finding maximum cardinality matchings, are not known to be much easier (on sparse graphs). The best algorithms for these problems also run in Õ(m√n) time. In this paper we present the first near-linear time algorithm for computing (1 - e)-approximate MWMs. Specifically, given an arbitrary real-weighted graph and ϵ > 0, our algorithm computes such a matching in O(mϵ-2log3n) time. The previous best approximate MWM algorithm with comparable running time could only guarantee a (2/3 - ϵ)-approximate solution. In addition, we present a faster algorithm, running in O(m log n log ϵ-1) time, that computes a (3/4 - ϵ)-approximate MWM.

A 0–1 matrix A is said to avoid a forbidden 0–1 matrix (or pattern) P if no submatrix of A matches P, where a 0 in P matches either 0 or 1 in A. The theory of forbidden matrices subsumes many extremal problems in combinatorics and graph theory such as bounding the length of Davenport-Schinzel sequences and their generalizations, Stanley and Wilf's permutation avoidance problem, and Turán-type subgraph avoidance problems. In addition, forbidden matrix theory has proved to be a powerful tool in discrete geometry and the analysis of both geometric and non-geometric algorithms. Clearly a 0–1 matrix can be interpreted as the incidence matrix of a bipartite graph in which vertices on each side of the partition are ordered. Our primary contribution is a refutation of a conjecture of Füredi and Hajnal: that if P corresponds to an acyclic graph then the maximum number of 1s in an n × n matrix avoiding P is O(n log n). In addition, we give a simpler proof that there are infinitely many minimal nonlinear patterns and give tight bounds on the extremal functions for several small forbidden patterns.

In this paper we improve, reprove, and simplify several theorems on the performance of data structures based on path compression and search trees. We apply a technique very familiar to computational geometers but still foreign to many researchers in (non-geometric) algorithms and data structures, namely, to bound the complexity of an object via its forbidden substructures.

Dynamic graph connectivity algorithms have been studied for many years, but typically in the most general possible setting, where the graph can evolve in completely arbitrary ways. In this paper we consider a dynamic subgraph model. We assume there is some fixed, underlying graph that can be preprocessed ahead of time. The graph is subject only to vertices and edges flipping "off" (failing) and "on" (recovering), where queries naturally apply to the subgraph on edges/vertices currently flipped on. This model fits most real world scenarios, where the topology of the graph in question (say a router network or road network) is constantly evolving due to temporary failures but never deviates too far from the ideal failure-free state.

An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a (multiplicative) (2 k −1, 0)-spanner of size O ( n 1+1/ k ) and an (additive) (1,2)-spanner of size O ( n 3/2 ). However no other additive spanners are known to exist. In this article we develop a couple of new techniques for constructing (α, β)-spanners. Our first result is an additive (1,6)-spanner of size O ( n 4/3 ). The construction algorithm can be understood as an economical agent that assigns costs and values to paths in the graph, purchasing affordable paths and ignoring expensive ones, which are intuitively well approximated by paths already purchased. We show that this path buying algorithm can be parameterized in different ways to yield other sparseness-distortion tradeoffs. Our second result addresses the problem of which (α, β)-spanners can be computed efficiently, ideally in linear time. We show that, for any k , a ( k , k −1)-spanner with size O ( kn 1+1/ k ) can be found in linear time, and, further, that in a distributed network the algorithm terminates in a constant number of rounds. Previous spanner constructions with similar performance had roughly twice the multiplicative distortion.

Given a directed graph with a capacity on each edge, the all-pairs bottleneck paths (APBP) problem is to determine, for all vertices s and t, the maximum flow that can be routed from s to t. For dense graphs this problem is equivalent to that of computing the (max, min)-transitive closure of a real-valued matrix. In this paper, we give a (max, min)-matrix multiplication algorithm running in time O(n(3+ω)/2) ≤ O(n2.688), where ω is the exponent of binary matrix multiplication. Our algorithm improves on a recent O(n2+ω/3) ≤ O(n2.792)-time algorithm of Vassilevska, Williams, and Yuster. Although our algorithm is slower than the best APBP algorithm on vertex capacitated graphs, running in O(n2.575) time, it is just as efficient as the best algorithm for computing the dominance product, a problem closely related to (max, min)-matrix multiplication. Our techniques can be extended to give subcubic algorithms for related bottleneck problems. The all-pairs bottleneck shortest paths problem (APBSP) asks for the maximum flow that can be routed along a shortest path. We give an APBSP algorithm for edge-capacitated graphs running in O(n(3+ω)/2) time and a slightly faster O(n2.657)-time algorithm for vertex-capactitated graphs. The second algorithm significantly improves on an O(n2.859)-time APBSP algorithm of Shapira, Yuster, and Zwick. Our APBSP algorithms make use of new hybrid products we call the distance-max-min product and dominance-distance product.

Spontaneous failure is an unavoidable aspect of all networks, particularly those with a physical basis such as communications networks or road networks. Whether due to malicious coordinated attacks or other causes, failures temporarily change the topology of the network and, as a consequence, its connectivity and distance metric. In this paper we look at the problem of efficiently answering connectivity, distance, and shortest route queries in the presence of two node or link failures. Our data structure uses Õ(n2) space and answers queries in Õ(1) time, which is within a polylogarithmic factor of optimal and nearly matches the single-failure distance oracles of Demestrescu et al. It may yet be possible to find distance/connectivity oracles capable of handling any fixed number of failures. However, the sheer complexity of our algorithm suggests that moving beyond dual-failures will require a fundamentally different approach to the problem.

A spanner of an undirected unweighted graph is a subgraph that approximates the distance metric of the original graph with some specified accuracy. Specifically, we say H ⊆ G is an f -spanner of G if any two vertices u , v at distance d in G are at distance at most f ( d ) in H . There is clearly some trade-off between the sparsity of H and the distortion function f , though the nature of the optimal trade-off is still poorly understood. In this article we present a simple, modular framework for constructing sparse spanners that is based on interchangable components called connection schemes . By assembling connection schemes in different ways we can recreate the additive 2- and 6-spanners of Aingworth et al. [1999] and Baswana et al. [2009], and give spanners whose multiplicative distortion quickly tends toward 1. Our results rival the simplicity of all previous algorithms and provide substantial improvements (up to a doubly exponential reduction in edge density) over the comparable spanners of Elkin and Peleg [2004] and Thorup and Zwick [2006].

Heavyweight security analysis systems, such as taint analysis and dynamic type checking, are powerful technologies used to detect security vulnerabilities and software bugs. Traditional software implementations of these systems have high instrumentation overhead and suffer from significant performance impacts. To mitigate these slowdowns, a few hardware-assisted techniques have been recently proposed. However, these solutions incur a large memory overhead and require hardware platform support in the form of tagged memory systems and extended bus designs. Due to these costs and limitations, the deployment of heavyweight security analysis solutions is, as of today, limited to the research lab. In this paper, we describe Testudo, a novel hardware approach to heavyweight security analysis that is based on statistical sampling of a programpsilas dataflow. Our dynamic distributed debugging reduces the memory overhead to a small storage space by selectively sampling only a few tagged variables to analyze during any particular execution of the program. Our system requires only small hardware modifications: it adds a small sample cache to the main processor and extends the pipeline registers to propagate analysis tags. To gain high analysis coverage, we rely on a population of users to run the program, sampling a different random set of variables during each new run. We show that we can achieve high coverage analysis at virtually no performance impact, even with a reasonably-sized population of users. In addition, our approach even scales to heavyweight debugging techniques by keeping per-user runtime overheads low despite performing traditionally costly analyses. Moreover, the low hardware cost of our implementation allows it to be easily distributed across large user populations, leading to a higher level of security analysis coverage than previously.

We present efficient algorithms for computing very sparse low distortion spanners in distributed networks and prove some non-trivial lower bounds on the trade-off between time, sparseness, and distortion. All of our algorithms assume a synchronized distributed network, where relatively short messages may be communicated in each time step. Our first result is an O(log n)1+o(1)-time algorithm for finding a (2O(log* n)log n)-spanner with size O(n). Besides being nearly optimal in time and distortion, this algorithm appears to be the first that constructs a O(n)-size skeleton without requiring unbounded length messages or time proportional to the diameter of the network. Our second result is a new class of efficiently constructible (α,β)-spanners called Fibonacci spanners whose distortion improves with the distance being approximated. At their sparsest Fibonacci spanners can have nearly linear size O(n(log log n)φ) where φ = 1+☂5/2 is the golden ratio. As the distance increases the Fibonacci spanner's multiplicative distortion passes through four discrete stages, moving from logarithmic to doubly logarithmic, then into a period where it is constant, tending to 3, followed by another period tending to 1. On the lower bound side we prove that many recent sequential spanner constructions have no efficient counterparts in distributed networks, even if the desired distortion only needs to be achieved on the average or for a tiny fraction of the vertices. In particular, any distance preservers, purely additive spanners, or spanners with sublinear additive distortion must either be very dense, slow to construct, or have very weak guarantees on distortion.

We present improved algorithms for finding approximately optimal matchings in both weighted and unweighted graphs. For unweighted graphs, we give an algorithm providing >(1-ε-approximation in O(log n) time for any constant ε > 0. This result improves on the classical 1 over 2-approximation due to Israeli and Itai. As a by-product, we also provide an improved algorithm for unweighted matchings in bipartite graphs. In the context of weighted graphs, we give another algorithm which provides (1 over 2-ε) approximation in general graphs in O(log n)time. The latter result improves on the known (1 over 4-ε-approximation in O(log n)time.

For many fundamental problems there exist randomized algorithms that are asymptotically optimal and are superior to the best-known deterministic algorithm. Among these are the minimum spanning tree (MST) problem, the MST sensitivity analysis problem, the parallel connected components and parallel minimum spanning tree problems, and the local sorting and set maxima problems. (For the first two problems there are provably optimal deterministic algorithms with unknown, and possibly superlinear, running times.) One downside of the randomized methods for solving these problems is that they use a number of random bits linear in the size of input. In this article we develop some general methods for reducing exponentially the consumption of random bits in comparison-based algorithms. In some cases we are able to reduce the number of random bits from linear to nearly constant, without affecting the expected running time. Most of our results are obtained by adjusting or reorganizing existing randomized algorithms to work well with a pairwise or O (1)-wise independent sampler. The prominent exception, and the main focus of this article, is a linear-time randomized minimum spanning tree algorithm that is not derived from the well-known Karger-Klein-Tarjan algorithm. In many ways it resembles more closely the deterministic minimum spanning tree algorithms based on soft heaps. Further, using our algorithm as a guide, we present a unified view of the existing “nongreedy” minimum spanning tree algorithms. Concepts from the Karger-Klein-Tarjan algorithm, such as F -lightness, MST verification, and sampled graphs, are related to the concepts of edge corruption, subgraph contractibility, and soft heaps, which are the basis of the deterministic MST algorithms of Chazelle and Pettie-Ramachandran.

Fredman, Sedgewick, Sleator and Tarjan proposed the pairing heap as a self-adjusting, streamlined version of the Fibonacci heap. It provably supports all priority queue operations in logarithmic time and is known to be extremely efficient in practice. However despite its simplicity and empirical superiority, the pairing heap is one of the few popular data structures whose basic complexity remains open. In this paper we prove that pairing heaps support the deletemin operation in optimal logarithmic time and all other operations (insert, meld, and decreasekey) in time O(2/sup 2 /spl radic/(log log n)/). This result gives the first sub-logarithmic time bound for decreasekey and comes close to the lower bound of /spl Omega/(log log n) established by Fredman. Pairing heaps have a well known but poorly understood relationship to splay trees and, to date, the transfer of ideas has flowed in one direction: from splaying to pairing. One contribution of this paper is a new analysis that reasons explicitly with information-theoretic measures. Whether these ideas could contribute to the analysis of splay trees is an open question.

We present a deterministic algorithm for computing the sensitivity of a minimum spanning tree (MST) or shortest path tree in O(mlogα(m,n)) time, where α is the inverse-Ackermann function. This improves upon a long standing bound of O(mα(m,n)) established by Tarjan. Our algorithms are based on an efficient split-findmin data structure, which maintains a collection of sequences of weighted elements that may be split into smaller subsequences. As far as we are aware, our split-findmin algorithm is the first with superlinear but sub-inverse-Ackermann complexity. We also give a reduction from MST sensitivity to the MST problem itself. Together with the randomized linear time MST algorithm of Karger, Klein, and Tarjan, this gives another randomized linear time MST sensitivity algorithm.

We present a new scheme for computing shortest paths on real-weighted undirected graphs in the fundamental comparison-addition model. In an efficient preprocessing phase our algorithm creates a linear-size structure that facilitates single-source shortest path computations in O(m log $\alpha$) time, where $\alpha$ = $\alpha$(m,n) is the very slowly growing inverse-Ackermann function, m the number of edges, and n the number of vertices. As special cases our algorithm implies new bounds on both the all-pairs and single-source shortest paths problems. We solve the all-pairs problem in O(mn log $\alpha$(m,n)) time and, if the ratio between the maximum and minimum edge lengths is bounded by n (log n) O(1) , we can solve the single-source problem in O(m + n log log n) time. Both these results are theoretical improvements over Dijkstra's algorithm, which was the previous best for real weighted undirected graphs. Our algorithm takes the hierarchy-based approach invented by Thorup.

We consider the problem of preprocessing an edge-weighted tree T in order to quickly answer queries of the following type: does a given edge e belong in the minimum spanning tree of T /spl cup/ {e}? Whereas the offline minimum spanning tree verification problem admits a lovely linear time solution, we demonstrate an inherent inverse-Ackermann type tradeoff in the online MST verification problem. In particular, any scheme that answers queries in t comparisons must invest /spl Omega/(n log /spl lambda//sub t/ (n)) time preprocessing the tree, where /spl lambda//sub t/ is the inverse of the t/sup th/ row of Ackermann's function. This implies a query lower bound of /spl Omega/(/spl alpha/(n)) for the case of linear preprocessing time. We also show that our lower bound is tight to within a factor of 2 in the t parameter.

We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically, we present a deterministic algorithm to find a minimum spanning tree of a graph with n vertices and m edges that runs in time O ( T * ( m,n )) where T * is the minimum number of edge-weight comparisons needed to determine the solution. The algorithm is quite simple and can be implemented on a pointer machine.Although our time bound is optimal, the exact function describing it is not known at present. The current best bounds known for T * are T * ( m,n ) = Ω( m ) and T * ( m,n ) = O ( m ∙ α( m,n )), where α is a certain natural inverse of Ackermann's function.Even under the assumption that T * is superlinear, we show that if the input graph is selected from G n,m , our algorithm runs in linear time with high probability, regardless of n , m , or the permutation of edge weights. The analysis uses a new martingale for G n,m similar to the edge-exposure martingale for G n,p .

We present a randomized algorithm to find a minimum spanning forest (MSF) in an undirected graph. With high probability, the algorithm runs in logarithmic time and linear work on an exclusive read exclusive write (EREW) PRAM. This result is optimal w.r.t. both work and parallel time, and is the first provably optimal parallel algorithm for this problem under both measures. We also give a simple, general processor allocation scheme for tree-like computations.