Exponentially Faster Shortest Paths in the Congested Clique

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+ϵ,\beta )$-approximation of APSP where $\beta=O(\frac{\log\log n}{\epsilon})^{\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{\beta }{ϵ})$ where $\beta =O(\frac{\log \log n}{ϵ}{)}^{\log \log n}$. Handling the long distances is done by devising a new algorithm for computing sparse $(1+ϵ,\beta )$ 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.