Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time   We consider the problem of building Distance Sensitivity Oracles (DSOs).
Given a directed graph $G=(V, E)$ with edge weights in $\{1, 2, \dots, M\}$, we
need to preprocess it into a data structure, and answer the following queries:
given vertices $u,v\in V$ and a failed vertex or edge $f\in (V\cup E)$, output
the length of the shortest path from $u$ to $v$ that does not go through $f$.
Our main result is a simple DSO with $\tilde{O}(n^{2.7233}M)$ preprocessing
time and $O(1)$ query time. Moreover, if the input graph is undirected, the
preprocessing time can be improved to $\tilde{O}(n^{2.6865}M)$. The
preprocessing algorithm is randomized with correct probability $\ge 1-1/n^C$,
for a constant $C$ that can be made arbitrarily large. Previously, there is a
DSO with $\tilde{O}(n^{2.8729}M)$ preprocessing time and
$\operatorname{polylog}(n)$ query time [Chechik and Cohen, STOC'20].
  At the core of our DSO is the following observation from [Bernstein and
Karger, STOC'09]: if there is a DSO with preprocessing time $P$ and query time
$Q$, then we can construct a DSO with preprocessing time $P+\tilde{O}(n^2)\cdot
Q$ and query time $O(1)$. (Here $\tilde{O}(\cdot)$ hides
$\operatorname{polylog}(n)$ factors.)

31
The categories of this paper are: ao-sci
14
The categories of this paper are: math-ph
33
The categories of this paper are: plasm-ph
18
The categories of this paper are: econ
22
The categories of this paper are: chao-dyn
0
The categories of this paper are: hep-ph
23
The categories of this paper are: solv-int
4
The categories of this paper are: cond-mat
36
The categories of this paper are: cmp-lg
35
The categories of this paper are: mtrl-th
6
The categories of this paper are: astro-ph
13
The categories of this paper are: quant-ph
37
The categories of this paper are: supr-con
30
The categories of this paper are: q-alg
24
The categories of this paper are: dg-ga
15
The categories of this paper are: nucl-ex