  Suppose we are given an $n$-node, $m$-edge input graph $G$, and the goal is
to compute a spanning subgraph $H$ on $O(n)$ edges. This can be achieved in
linear $O(m + n)$ time via breadth-first search. But can we hope for
\emph{sublinear} runtime in some range of parameters?
  If the goal is to return $H$ as an adjacency list, there are simple lower
bounds showing that $\Omega(m + n)$ runtime is necessary. If the goal is to
return $H$ as an adjacency matrix, then we need $\Omega(n^2)$ time just to
write down the entries of the output matrix. However, we show that neither of
these lower bounds still apply if instead the goal is to return $H$ as an
\emph{implicit} adjacency matrix, which we call an \emph{adjacency oracle}. An
adjacency oracle is a data structure that gives a user the illusion that an
adjacency matrix has been computed: it accepts edge queries $(u, v)$, and it
returns in near-constant time a bit indicating whether $(u, v) \in E(H)$.
  Our main result is that one can construct an adjacency oracle for a spanning
subgraph on at most $(1+\varepsilon)n$ edges, in $\tilde{O}(n
\varepsilon^{-1})$ time, and that this construction time is near-optimal.
Additional results include constructions of adjacency oracles for
$k$-connectivity certificates and spanners, which are similarly sublinear on
dense-enough input graphs.
  Our adjacency oracles are closely related to Local Computation Algorithms
(LCAs) for graph sparsifiers; they can be viewed as LCAs with some computation
moved to a preprocessing step, in order to speed up queries. Our oracles imply
the first Local algorithm for computing sparse spanning subgraphs of general
input graphs in $\tilde{O}(n)$ query time, which works by constructing our
adjacency oracle, querying it once, and then throwing the rest of the oracle
away. This addresses an open problem of Rubinfeld [CSR '17].

Data Structures and Algorithms