  The success of modern parallel paradigms such as MapReduce, Hadoop, or Spark,
has attracted a significant attention to the Massively Parallel Computation
(MPC) model over the past few years, especially on graph problems. In this
work, we consider symmetry breaking problems of maximal independent set (MIS)
and maximal matching (MM), which are among the most intensively studied
problems in distributed/parallel computing, in MPC.
  These problems are known to admit efficient MPC algorithms if the space per
machine is near-linear in $n$, the number of vertices in the graph. This space
requirement however, as observed in the literature, is often significantly
larger than we can afford; especially when the input graph is sparse. In a
sharp contrast, in the truly sublinear regime of $n^{1-\Omega(1)}$ space per
machine, all the known algorithms take $\log^{\Omega(1)} n$ rounds which is
considered inefficient.
  Motivated by this shortcoming, we parametrize our algorithms by the
arboricity $\alpha$ of the input graph, which is a well-received measure of its
sparsity. We show that both MIS and MM admit $O(\sqrt{\log \alpha}\cdot\log\log
\alpha + \log^2\log n)$ round algorithms using $O(n^\epsilon)$ space per
machine for any constant $\epsilon \in (0, 1)$ and using $\widetilde{O}(m)$
total space. Therefore, for the wide range of sparse graphs with small
arboricity---such as minor-free graphs, bounded-genus graphs or bounded
treewidth graphs---we get an $O(\log^2 \log n)$ round algorithm which
exponentially improves prior algorithms.
  By known reductions, our results also imply a $(1+\epsilon)$-approximation of
maximum cardinality matching, a $(2+\epsilon)$-approximation of maximum
weighted matching, and a 2-approximation of minimum vertex cover with
essentially the same round complexity and memory requirements.
