  We introduce a method for sparsifying distributed algorithms and exhibit how
it leads to improvements that go past known barriers in two algorithmic
settings of large-scale graph processing: Massively Parallel Computation (MPC),
and Local Computation Algorithms (LCA).
  - MPC with Strongly Sublinear Memory: Recently, there has been growing
interest in obtaining MPC algorithms that are faster than their classic $O(\log
n)$-round parallel counterparts for problems such as MIS, Maximal Matching,
2-Approximation of Minimum Vertex Cover, and $(1+\epsilon)$-Approximation of
Maximum Matching. Currently, all such MPC algorithms require
$\tilde{\Omega}(n)$ memory per machine. Czumaj et al. [STOC'18] were the first
to handle $\tilde{\Omega}(n)$ memory, running in $O((\log\log n)^2)$ rounds. We
obtain $\tilde{O}(\sqrt{\log \Delta})$-round MPC algorithms for all these four
problems that work even when each machine has memory $n^{\alpha}$ for any
constant $\alpha\in (0, 1)$. Here, $\Delta$ denotes the maximum degree. These
are the first sublogarithmic-time algorithms for these problems that break the
linear memory barrier.
  - LCAs with Query Complexity Below the Parnas-Ron Paradigm: Currently, the
best known LCA for MIS has query complexity $\Delta^{O(\log \Delta)} poly(\log
n)$, by Ghaffari [SODA'16]. As pointed out by Rubinfeld, obtaining a query
complexity of $poly(\Delta\log n)$ remains a central open question. Ghaffari's
bound almost reaches a $\Delta^{\Omega\left(\frac{\log \Delta}{\log\log
\Delta}\right)}$ barrier common to all known MIS LCAs, which simulate
distributed algorithms by learning the local topology, \`{a} la Parnas-Ron
[TCS'07]. This barrier follows from the $\Omega(\frac{\log \Delta}{\log\log
\Delta})$ distributed lower bound of Kuhn, et al. [JACM'16]. We break this
barrier and obtain an MIS LCA with query complexity $\Delta^{O(\log\log
\Delta)} poly(\log n)$.
