Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces the first deterministic algorithms with sublogarithmic round complexity for spanners and approximate shortest paths in various models of multiparty computation (MPC). The authors achieve significant advancements in the Congested Clique model, providing efficient algorithms for both linear and sublinear MPC that yield stretch-spanners and approximate shortest paths with improved round complexities. Notably, they derive an $O(\log n)$ approximation of all-pairs shortest paths (APSP) in constant rounds for large graphs, matching the performance of state-of-the-art randomized methods without the associated round complexity penalties.
Achieving $O(\log n)$ approximation of APSP in constant rounds could revolutionize efficiency in multiparty computation settings.
In this paper, we provide the first deterministic algorithms with sublogarithmic round complexity for spanners and approximate shortest paths in various MPC models. Moreover, we significantly improve upon the state of the art in the deterministic Congested Clique. In particular, we obtain the following four results on undirected graphs: 1. In both linear MPC and Congested Clique, we obtain an $O(k)$ stretch-spanner of a weighted graph of size $O(n^{1+1/k})$ in $O(1)$ rounds, for some parameter $k\ge 0$. For $k=O(\log{n})$, this leads to an $O(\log n)$ approximation of APSP in constant rounds in both models. 2. In sublinear MPC, we obtain an $O(k^{1+\varepsilon})$-stretch spanner of a weighted graph of size $O(n^{1+1/k})$ in $O(\log k)$ rounds, for any fixed constant $\varepsilon>0$. 3. In Congested Clique, we obtain $O(1)$-approximate APSP for weighted graphs in $O(\log \log \log n)$ rounds. 4. In near-linear MPC, we obtain $(1+\varepsilon)$-approximate single-source shortest paths and $O(1)$-approximate all-pairs shortest paths for unweighted graphs in $\textsf{poly}\log \log n$ rounds. Our algorithm only requires a single near-linear memory machine, where the rest can have sublinear memory. Our deterministic algorithms obtain similar guarantees to the state of the art randomized algorithms without incurring additional factors in the round complexity. To obtain these results, we inspect the randomized algorithms and isolate a randomized sampling routine. Then we derandomize these sampling routines by using a deterministic hitting set. Hereto, we develop a versatile deterministic hitting set algorithm, which we hope will have further derandomization applications.