  Estimating the size of the maximum matching is a canonical problem in graph
algorithms, and one that has attracted extensive study over a range of
different computational models. We present improved streaming algorithms for
approximating the size of maximum matching with sparse (bounded arboricity)
graphs.
  * Insert-Only Streams: We present a one-pass algorithm that takes O(c log^2
n) space and approximates the size of the maximum matching in graphs with
arboricity c within a factor of O(c). This improves significantly on the
state-of-the-art O~(cn^{2/3})-space streaming algorithms.
  * Dynamic Streams: Given a dynamic graph stream (i.e., inserts and deletes)
of edges of an underlying c-bounded arboricity graph, we present a one-pass
algorithm that uses space O~(c^{10/3}n^{2/3}) and returns an O(c)-estimator for
the size of the maximum matching. This algorithm improves the state-of-the-art
O~(cn^{4/5})-space algorithms, where the O~(.) notation hides logarithmic in
$n$ dependencies.
  In contrast to the previous works, our results take more advantage of the
streaming access to the input and characterize the matching size based on the
ordering of the edges in the stream in addition to the degree distributions and
structural properties of the sparse graphs.
