# Exponentially Faster Shortest Paths in the Congested Clique

Preprint · Michal Dory, Merav Parter

- Archive id: arxiv:2003.03058
- Published: 2020-03-06
- arXiv: https://arxiv.org/abs/2003.03058
- Citations: 0
- Source URL: https://arxiv.org/abs/2003.03058
- PDF: https://arxiv.org/pdf/2003.03058
- Provenance: arxiv

## Abstract

We present improved deterministic algorithms for approximating shortest paths in the Congested Clique model of distributed computing. We obtain $poly(\\log\\log n)$-round algorithms for the following problems in unweighted undirected $n$-vertex graphs: -- $(1+ε)$-approximation of multi-source shortest paths (MSSP) from $O(\\sqrt{n})$ sources. -- $(2+ε)$-approximation of all pairs shortest paths (APSP). -- $(1+ε,β)$-approximation of APSP where $β=O(\\frac{\\log\\log n}ε)^{\\log\\log n}$. These bounds improve exponentially over the state-of-the-art poly-logarithmic bounds due to \[Censor-Hillel et al., PODC19\]. It also provides the first nearly-additive bounds for the APSP problem in sub-polynomial time. Our approach is based on distinguishing between short and long distances based on some distance threshold $t = O(\\fracβε)$ where $β=O(\\frac{\\log\\log n}ε)^{\\log\\log n}$. Handling the long distances is done by devising a new algorithm for computing sparse $(1+ε,β)$ emulator with $O(n\\log\\log n)$ edges. For the short distances, we provide distance-sensitive variants for the distance tool-kit of \[Censor-Hillel et al., PODC19\]. By exploiting the fact that this tool-kit should be applied only on local balls of radius $t$, their round complexities get improved from $poly(\\log n)$ to $poly(\\log t)$. Finally, our deterministic solutions for these problems are based on a derandomization scheme of a novel variant of the hitting set problem, which might be of independent interest.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.