We design fast deterministic algorithms for distance computation in the congested clique model. Our key contributions include: -- A @math -approximation for all-pairs shortest paths in @math rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model. -- A @math -approximation for multi-source shortest paths from @math sources in @math rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size. Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in @math rounds.
   For a positive parameter @math , the @math -bounded distance between a pair of vertices @math in a weighted undirected graph @math is the length of the shortest @math path in @math with at most @math edges, aka hops . For @math as above and @math , a @math -hopset of @math is a graph @math on the same vertex set, such that all distances in @math are @math -approximated by @math -bounded distances in @math . Hopsets are a fundamental graph-theoretic and graph-algorithmic construct, and they are widely used for distance-related problems in a variety of computational settings. Currently existing constructions of hopsets produce hopsets either with @math edges, or with a hopbound @math . In this paper we devise a construction of linear-size hopsets with hopbound @math . This improves the previous bound almost exponentially. We also devise efficient implementations of our construction in PRAM and distributed settings. The only existing PRAM algorithm EN16 for computing hopsets with a constant (i.e., independent of @math ) hopbound requires @math time. We devise a PRAM algorithm with polylogarithmic running time for computing hopsets with a constant hopbound, i.e., our running time is exponentially better than the previous one. Moreover, these hopsets are also significantly sparser than their counterparts from EN16 . We use our hopsets to devise a distributed routing scheme that exhibits near-optimal tradeoff between individual memory requirement @math of vertices throughout preprocessing and routing phases of the algorithm, and stretch @math , along with a near-optimal construction time @math , where @math is the hop-diameter of the input graph.  Let k ≥ 2 be an integer. We show that any undirected and unweighted graph G = (V, E) on n vertices has a subgraph G' = (V, E') with O(kn1+1 k) edges such that for any two vertices u, v ∈ V, if Δ G (u, v) = d, then Δ G' (u, v) = d+O(d1-1 k-1). Furthermore, we show that such subgraphs can be constructed in O(mn1 k) time, where m and n are the number of edges and vertices in the original graph. We also show that it is possible to construct a weighted graph G* = (V, E*) with O(kn1+1 (2k-1)) edges such that for every u, v ∈ V, if Δ G (u, v) = d, then Δ ≤ Δ G* (u, v) = d + O(d1-1 k-1). These are the first such results with additive error terms of the form o(d), i.e., additive error terms that are sublinear in the distance being approximated. Abstract A ( β , ϵ ) -hopset is, informally, a weighted edge set that, when added to a graph, allows one to get from point a to point b using a path with at most β edges (“hops”) and length ( 1 + ϵ ) dist ( a , b ) . In this paper we observe that Thorup and Zwick's sublinear additive emulators are also actually ( O ( k ϵ ) k , ϵ ) -hopsets for every ϵ > 0 , and that with a small change to the Thorup–Zwick construction, the size of the hopset can be made O ( n 1 + 1 2 k + 1 − 1 ) . As corollaries, we also shave “k” factors off the size of Thorup and Zwick's [20] sublinear additive emulators and the sparsest known ( 1 + ϵ , O ( k ϵ ) k − 1 ) -spanners, due to Abboud, Bodwin, and Pettie [1] . Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say @math bits. There ...    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]. 