Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: 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+\epsilon)$-approximation of multi-source shortest paths (MSSP) from
$O(\sqrt{n})$ sources.
  -- $(2+\epsilon)$-approximation of all pairs shortest paths (APSP).
  -- $(1+\epsilon,\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}{\epsilon})$ where
$\beta=O(\frac{\log\log n}{\epsilon})^{\log\log n}$. Handling the long
distances is done by devising a new algorithm for computing sparse
$(1+\epsilon,\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.

22
The categories of this paper are: chao-dyn
0
The categories of this paper are: hep-ph
29
The categories of this paper are: funct-an
27
The categories of this paper are: comp-gas
9
The categories of this paper are: nlin
10
The categories of this paper are: q-bio
7
The categories of this paper are: hep-th
35
The categories of this paper are: mtrl-th
32
The categories of this paper are: atom-ph
25
The categories of this paper are: patt-sol
20
The categories of this paper are: acc-phys
11
The categories of this paper are: hep-lat
13
The categories of this paper are: quant-ph
23
The categories of this paper are: solv-int
19
The categories of this paper are: eess
12
The categories of this paper are: nucl-th