MPVX15 devised a distributed They actually showed a PRAM algorithm. The distributed algorithm with these properties is implicit in MPVX15 . algorithm in the CONGEST model, that given a parameter @math , constructs an @math -spanner of an input unweighted @math -vertex graph with @math expected edges in @math rounds of communication. In this paper we improve the result of MPVX15 , by showing a @math -round distributed algorithm in the same model, that constructs a @math -spanner with @math edges, with probability @math , for any @math . Moreover, when @math , our algorithm produces (still in @math rounds) ultra-sparse spanners, i.e., spanners of size @math , with probability @math . To our knowledge, this is the first distributed algorithm in the CONGEST or in the PRAM models that constructs spanners or skeletons (i.e., connected spanning subgraphs) that sparse. Our algorithm can also be implemented in linear time in the standard centralized model, and for large @math , it provides spanners that are sparser than any other spanner given by a known (near-)linear time algorithm. We also devise improved bounds (and algorithms realizing these bounds) for @math -spanners and emulators. In particular, we show that for any unweighted @math -vertex graph and any @math , there exists a @math -emulator with @math edges. All previous constructions of @math -spanners and emulators employ a superlinear number of edges, for all choices of parameters. Finally, we provide some applications of our results to approximate shortest paths' computation in unweighted graphs.
Efficient algorithms for constructing @math -spanners were also devised in @cite_50 @cite_43 @cite_47 @cite_35 @cite_24 . These algorithms are based, however, on different approaches than that of the current paper. The latter is based on @cite_6 . Specifically, the approach of @cite_50 @cite_43 is based on @cite_21 @cite_28 construction of pairwise covers and hopsets, i.e., the algorithm works top-down. It recurses in small clusters, and eliminates large ones. The approach of @cite_47 @cite_35 @cite_24 is based on @cite_61 collection of trees, used originally for distance oracles. Streaming algorithms for constructing multiplicative spanners were given in @cite_9 @cite_27 @cite_16 , and near-additive spanners in @cite_50 @cite_43 . Spanners and emulators with sublinear error were given in @cite_47 @cite_35 . Spanners with purely additive error and lower bounds concerning them were given in @cite_7 @cite_6 @cite_12 @cite_3 @cite_52 @cite_26 @cite_1 @cite_8 .
@cite_35 @cite_3 @cite_43 @cite_8 @cite_21 @cite_52 @cite_26 @cite_7 @cite_28 @cite_6 @cite_27 @cite_50 @cite_16 @cite_12 @cite_61 @cite_9 @cite_1 @cite_24 @cite_47
2809995963 2227069303 2508647357 2032654248 2099237198 2033607935 2122632420 1574233320 2092938419 1986144992 2093429583 2000931246 2963530558 1972920042 2562627112 2221370457 1637999745 2042333226 816673839 1982831910
An (α,β)-spanner of an n-vertex graph G = (V,E) is a subgraph H of G satisfying that dist(u, v, H) ≤ α·dist(u, v, G) + β for every pair (u, v) ∈ V ×V, where dist(u,v,G′) denotes the distance between u and v in G′ ⊆ G. It is known that for every integer k ≥ 1, every graph G has a polynomially constructible (2k − 1,0)-spanner of size O(n 1 + 1 k ). This size-stretch bound is essentially optimal by the girth conjecture. Yet, it is important to note that any argument based on the girth only applies to adjacent vertices. It is therefore intriguing to ask if one can “bypass” the conjecture by settling for a multiplicative stretch of 2k − 1 only for neighboring vertex pairs, while maintaining a strictly better multiplicative stretch for the rest of the pairs. We answer this question in the affirmative and introduce the notion of k-hybrid spanners, in which non neighboring vertex pairs enjoy a multiplicative k stretch and the neighboring vertex pairs enjoy a multiplicative (2k − 1) stretch (hence, tight by the conjecture). We show that for every unweighted n-vertex graph G, there is a (polynomially constructible) k-hybrid spanner with O(k 2 ·n 1 + 1 k ) edges. This should be compared against the current best (α,β) spanner construction of [5] that obtains (k,k − 1) stretch with O(k ·n 1 + 1 k ) edges. An alternative natural approach to bypass the girth conjecture is to allow ourself to take care only of a subset of pairs S ×V for a given subset of vertices S ⊆ V referred to here as sources. Spanners in which the distances in S ×V are bounded are referred to as sourcewise spanners. Several constructions for this variant are provided (e.g., multiplicative sourcewise spanners, additive sourcewise spanners and more). A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality of its approximation, so long as distance error is measured multiplicatively. A central open question in the field is to prove or disprove whether such a tradeoff exists also in the regime of additive error. That is, is it true that for all e>0, there is a constant ke such that every graph has a spanner on O(n1+e) edges that preserves its pairwise distances up to +ke? Previous lower bounds are consistent with a positive resolution to this question, while previous upper bounds exhibit the beginning of a tradeoff curve: all graphs have +2 spanners on O(n3 2) edges, +4 spanners on O(n7 5) edges, and +6 spanners on O(n4 3) edges. However, progress has mysteriously halted at the n4 3 bound, and despite significant effort from the community, the question has remained open for all 0 Our main result is a surprising negative resolution of the open question, even in a highly generalized setting. We show a new information theoretic incompressibility bound: there is no function that compresses graphs into O(n4 3 − e) bits so that distance information can be recovered within +no(1) error. As a special case of our theorem, we get a tight lower bound on the sparsity of additive spanners: the +6 spanner on O(n4 3) edges cannot be improved in the exponent, even if any subpolynomial amount of additive error is allowed. Our theorem implies new lower bounds for related objects as well; for example, the twenty-year-old +4 emulator on O(n4 3) edges also cannot be improved in the exponent unless the error allowance is polynomial. Central to our construction is a new type of graph product, which we call the Obstacle Product. Intuitively, it takes two graphs G,H and produces a new graph G H whose shortest paths structure looks locally like H but globally like G. Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say O(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 Δ 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 [EQUATION] has a sublinear additive stretch function f: f(d) = d + Ω(d1−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 + ϵ, β)-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 [EQUATION], where hk 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 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γ + 1. One consequence is that 's (2010) additive O(γ)-spanners with size [EQUATION] cannot be improved in the exponent. 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. 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) (2k−1, 0)-spanner of size O(n1+1 k) and an (additive) (1,2)-spanner of size O(n3 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(n4 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(kn1+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. We present efficient algorithms for computing very sparse low distortion spanners in distributed networks and prove some non-trivial lower bounds on the tradeoff 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 a fast distributed algorithm for finding an ( O(2^ 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 an 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, namely ( O(n( n)^ ) ) , where ( = (1 + 5 ) 2 ) is the golden ratio. As the distance increases the multiplicative distortion of a Fibonacci spanner passes through four discrete stages, moving from logarithmic to log-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. For an unweighted undirected graph G= (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G'= (V,H), H ⊆ E, is called an (α,β)-spanner of G if for every pair of vertices u, v ∈ V, dist G' (u,v) ≤ α • dist G' (u,v) + β.It was shown in [20] that for any e > 0, κ = 1,2, ..., there exists an integer β = β(e,κ) such that for every n-vertex graph G there exists a (1+e,β)-spanner G' with O(n1+1 κ) edges. An efficient distributed protocol for constructing (1+e,β)-spanners was devised in [18]. The running time and the communication complexity of that protocol are O(n1+ρ) and O(|E|nρ), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β.In this paper we devise a protocol with a drastically improved running time (O(nρ) as opposed to (O(n1+ρ) for constructing (1+e,β)-spanners. Our protocol has the same communication complexity as the protocol of [18], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [18].We also show that our protocol for constructing (1+e, β)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and O(n1+1 κ • log n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1 + e) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time O(nρ), for an arbitrarily small ρ > 0. The only previously known algorithm for the problem [21] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires O(n1+1 κ) time for processing each edge of the input graph. However, the algorithm of [21] uses just one pass over the input, as opposed to the constant number of passes in our algorithm. We also show that any streaming algorithm for o(n)-approximate distance computation requires Ω(n) bits of space. Let G(V, E) be an undirected weighted graph with |V| = n, and |E| = m. A t-spanner of the graph G(V, E) is a sub-graph G(V, ES) such that the distance between any pair of vertices in the spanner is at most t times the distance between the two in the given graph. A 1963 girth conjecture of Erdos implies that Ω(n1+1 k) edges are required in the worst case for any (2k - 1)-spanner, which has been proved for k = 1, 2, 3, 5. There exist polynomial time algorithms that can construct spanners with the size that matches this conjectured lower bound, and the best known algorithm takes O(mn1 k) expected running time. In this paper, we present an extremely simple linear time randomized algorithm that constructs (2k - 1)-spanner of size matching the conjectured lower bound. Our algorithm requires local information for computing a spanner, and thus can be adapted suitably to obtain efficient distributed and parallel algorithms. Let G = (V,E) be an undirected weighted graph on |V | = n vertices and |E| = m edges. A t-spanner of the graph G, for any t ≥ 1, is a subgraph (V,ES), ES ⊆ E, such that the distance between any pair of vertices in the subgraph is at most t times the distance between them in the graph G. Computing a t-spanner of minimum size (number of edges) has been a widely studied and well-motivated problem in computer science. In this paper we present the first linear time randomized algorithm that computes a t-spanner of a given weighted graph. Moreover, the size of the t-spanner computed essentially matches the worst case lower bound implied by a 43-year old girth lower bound conjecture made independently by Erdos, Bollobas, and Bondy & Simonovits. Our algorithm uses a novel clustering approach that avoids any distance computation altogether. This feature is somewhat surprising since all the previously existing algorithms employ computation of some sort of local or global distance information, which involves growing either breadth first search trees up to t(t)-levels or full shortest path trees on a large fraction of vertices. The truly local approach of our algorithm also leads to equally simple and efficient algorithms for computing spanners in other important computational environments like distributed, parallel, and external memory. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007 Preliminary version of this work appeared in the 30th International Colloquium on Automata, Languages and Programming, pages 384–396, 2003. We present an O(nlogn)-approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G=(V,E) with nonnegative edge lengths d:E->R^>=^0 and a stretchk>=1, a subgraph H=(V,E"H) is a k-spanner of G if for every edge (s,t)@?E, the graph H contains a path from s to t of length at most [email protected]?d(s,t). The previous best approximation ratio was [email protected]?(n^2^ ^3), due to Dinitz and Krauthgamer (STOC @?11). We also improve the approximation ratio for the important special case of directed 3-spanners with unit edge lengths from [email protected]?(n) to O(n^1^ ^3logn). The best previously known algorithms for this problem are due to Berman, Raskhodnikova and Ruan (FSTTCS @?10) and Dinitz and Krauthgamer. The approximation ratio of our algorithm almost matches Dinitz and [email protected]?s lower bound for the integrality gap of a natural linear programming relaxation. Our algorithm directly implies an O(n^1^ ^3logn)-approximation for the 3-spanner problem on undirected graphs with unit lengths. An easy O(n)-approximation algorithm for this problem has been the best known for decades. Finally, we consider the Directed Steiner Forest problem: given a directed graph with edge costs and a collection of ordered vertex pairs, find a minimum-cost subgraph that contains a path between every prescribed pair. We obtain an approximation ratio of O(n^2^ ^3^+^@e) for any constant @e>0, which improves the O(n^@[email protected]?min(n^4^ ^5,m^2^ ^3)) ratio due to Feldman, Kortsarz and Nutov ([email protected]?12). We obtain new upper bounds on the additive distortion for graph emulators and spanners on relatively few edges. We introduce a new subroutine called "strip creation," and we combine this subroutine with several other ideas to obtain the following results: Every graph has a spanner on O(n1+e) edges with O(n 1 2 - e 2) additive distortion, for arbitrary e ∈ [0,1]. Every graph has an emulator on O(n1+e) edges with O(n 1 3 -- 2e 3) additive distortion whenever e ∈ [0, 1 5]. Every graph has a spanner on O(n1 + e) edges with O(n2 3 -- 5e 3) additive distortion whenever e ∈ [0, 1 4]. Our first spanner has the new best known asymptotic edge-error tradeoff for additive spanners whenever e ∈ [0, 1 7]. Our second spanner has the new best tradeoff whenever e ∈ [1 7, 3 17]. Our emulator has the new best asymptotic edge-error tradeoff whenever e ∈ [0, 1 5]. Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253 [43] devised a distributed1 algorithm in the CONGEST model, that given a parameter k = 1, 2, ..., constructs an O(k)-spanner of an input unweighted n-vertex graph with O(n1+1 k) expected edges in O(k) rounds of communication. In this paper we improve the result of [43], by showing a k-round distributed algorithm in the same model, that constructs a (2k − 1)-spanner with O(n1+1 k ϵ) edges, with probability 1 − ϵ, for any ϵ > 0. Moreover, when k = ω(log n), our algorithm produces (still in k rounds) ultra-sparse spanners, i.e., spanners of size n(1 + o(1)), with probability 1 − o(1). To our knowledge, this is the first distributed algorithm in the CONGEST or in the PRAM models that constructs spanners or skeletons (i.e., connected spanning subgraphs) that sparse. Our algorithm can also be implemented in linear time in the standard centralized model, and for large k, it provides spanners that are sparser than any other spanner given by a known (near-)linear time algorithm. We also devise improved bounds (and algorithms realizing these bounds) for (1 + ϵ, β)-spanners and emulators. In particular, we show that for any unweighted n-vertex graph and any ϵ > 0, there exists a [EQUATION]-emulator with O(n) edges. All previous constructions of (1 + ϵ, β)-spanners and emulators employ a superlinear number of edges, for all choices of parameters. Finally, we provide some applications of our results to approximate shortest paths' computation in unweighted graphs. An additive spanner of an unweighted undirected graph G with distortion d is a subgraph H such that for any two vertices u, v G, we have _H ( u,v ) = _G ( u,v ) + d. For every k = O ( n n ), we construct a graph G on n vertices for which any additive spanner of G with distortion 2k - 1 has ( 1 k n^ 1 + 1 k ) edges. This matches the lower bound previously known only to hold under a 1963 conjecture of Erdos. We generalize our lower bound in a number of ways. First, we consider graph emulators introduced by Dor, Halperin, and Zwick (FOCS, 1996), where an emulator of an unweighted undirected graph G with distortion d is like an additive spanner except H may be an arbitrary weighted graph such that _G ( u,v ) _H ( u,v ) _G ( u,v ) + d. We show a lower bound of ( 1 k^2 n^ 1 + 1 k ) edges for distortion-(2k - 1) emulators. These are the first non-trivial bounds for k 3. Second, we parameterize our bounds in terms of the minimum degree of the graph. Namely, for minimum degree n^ 1 k+c for any c 0, we prove a bound of ( 1 k n^ 1 + 1 k - c(1 + 2 (k - 1)) ) for additive spanners and ( 1 k^2 n^ 1 + 1 k - c(1 + 2 (k - 1)) ) for emulators. For k = 2 these can be improved to ( n^ 3 2 - c ). This partially answers a question of (SODA, 2005) for additive spanners. Finally, we continue the study of pair-wise and source-wise distance preservers defined by Coppersmith and Elkin (SODA, 2005) by considering their approximate variants and their relaxation to emulators. We prove the first lower bounds for such graphs. Let G=(V,E) be an undirected unweighted graph on n vertices. A subgraph H of G is called an (all-pairs) purely additive spanner with stretch β if for every (u,v)∈V×V, d i s t H (u,v)≤d i s t G (u,v) + β. The problem of computing sparse spanners with small stretch β is well-studied. Here we consider the following variant: we are given ( P V V ) and we seek a sparse subgraph H where d i s t H (u,v)≤d i s t G (u,v) + β for each ((u,v) P ). That is, distances for pairs outside ( P ) need not be well-approximated in H. Such a subgraph is called a pairwise spanner with additive stretch β and our goal is to construct such subgraphs that are sparser than all-pairs spanners with the same stretch. We show sparse pairwise spanners with additive stretch 4 and with additive stretch 6. We also consider the following special cases: ( P = S V ) and ( P = S T ), where S⊆V and T⊆V, and show sparser pairwise spanners for these cases. This paper considers additive and purely additive spanners. We present a new purely additive spanner of size O(n7 5) with additive stretch 4. This construction fills in the gap between the two existing constructions for purely additive spanners, one for 2-additive spanner of size O(n3 2) and the other for 6-additive spanner of size O(n4 3), and thus answers a main open question in this area. In addition, we present a construction for additive spanners with O(n1+δ) edges and additive stretch of O(n1 2−3δ 2) for any 3 17 ≤ δ < 1 3, improving the stretch of the existing constructions from O(n1−3δ) to O(√n1−3δ). Finally, we show that our (1,n1 2−3δ 2)-spanner construction can be tweaked to give a sublinear additive spanner of size O(n1+3 17) with additive stretch O(√distance). We describe a new class of list decodable codes based on Galois extensions of function fields and present a list decoding algorithm. These codes are obtained as a result of folding the set of rational places of a function field using certain elements (automorphisms) from the Galois group of the extension. This work is an extension of Folded Reed Solomon codes to the setting of Algebraic Geometric codes. We describe two constructions based on this framework depending on if the order of the automorphism used to fold the code is large or small compared to the block length. When the automorphism is of large order, the codes have polynomially bounded list size in the worst case. This construction gives codes of rate @math over an alphabet of size independent of block length that can correct a fraction of @math errors subject to the existence of asymptotically good towers of function fields with large automorphisms. The second construction addresses the case when the order of the element used to fold is small compared to the block length. In this case a heuristic analysis shows that for a random received word, the expected list size and the running time of the decoding algorithm are bounded by a polynomial in the block length. When applied to the Garcia-Stichtenoth tower, this yields codes of rate @math over an alphabet of size @math , that can correct a fraction of @math errors. An @math -spanner of a graph G is a subgraph H such that @math for every pair of vertices u,w, where distG'(u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible @math -spanner (also known as multiplicative @math -spanner) of size @math for every integer @math , and a polynomially constructible (1,2)-spanner (also known as additive 2-spanner) of size @math . This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant @math there exists a constant @math such that for every @math -vertex graph G there is an efficiently constructible @math -spanner of size @math . We present a deterministic (1+o(1))-approximation O(n1 2+o(1)+D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation O(n1 2D1 4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n1 8, and (ii) the O(є−1logє−1)-approximation factor of Lenzen and Patt-Shamir’s O(n1 2+є+D)-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of Ω(n1 2 logn + D) [Das STOC 2011] modulo some lower-order terms, thus essentially settling the status of this problem which was raised at least a decade ago [Elkin SIGACT News 2004]. It also implies a (2+o(1))-approximation O(n1 2+o(1)+D1+o(1))-time algorithm for approximating a network’s weighted diameter which almost matches the lower bound by [PODC 2012]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic, construction of an (no(1), o(1))-hop set of size O(n1+o(1)). We combine these techniques with many distributed algorithmic techniques, some of which from problems that are not directly related to shortest paths, e.g. ruling sets [ STOC 1987], source detection [Lenzen, Peleg PODC 2013], and partial distance estimation [Lenzen, Patt-Shamir PODC 2015]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation O(no(1))-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation O(no(1)logW)-pass O(n1+o(1)logW)-space streaming algorithm, when edge weights are in 1, 2, …, W . The first result answers an open problem in [Nanongkai, STOC 2014]. The second result partially answers an open problem raised by McGregor in 2006 [ sublinear.info , Problem 14]. In this paper, we consider conic programming problems whose constraints consist of linear equalities, linear inequalities, a nonpolyhedral cone, and a polyhedral cone. A convenient way for solving this class of problems is to apply the directly extended alternating direction method of multipliers (ADMM) to its dual problem, which has been observed to perform well in numerical computations but may diverge in theory. Ideally, one should find a convergent variant which is at least as efficient as the directly extended ADMM in practice. We achieve this goal by designing a convergent semiproximal ADMM (called sPADMM3c for convenience) for convex programming problems having three separable blocks in the objective function with the third part being linear. At each iteration, the proposed sPADMM3c takes one special block coordinate descent (BCD) cycle with the order @math , instead of the usual @math Gauss--Seidel BCD cycle used in the nonconvergent directly extended 3-block ADMM, for updating the variable blocks. Our numerical experiments demonstrate that the convergent method is at least 20 faster than the directly extended ADMM with unit step-length for the vast majority of about 550 large-scale doubly nonnegative semidefinite programming problems with linear equality and or inequality constraints. This confirms that at least for conic convex programming, one can design a convergent and efficient ADMM with a special BCD cycle of updating the variable blocks.