  In this paper we present improved bounds for approximating maximum matchings
in bipartite graphs in the streaming model. First, we consider the question of
how well maximum matching can be approximated in a single pass over the input
using $\tilde O(n)$ space, where $n$ is the number of vertices in the input
graph. Two natural variants of this problem have been considered in the
literature: (1) the edge arrival setting, where edges arrive in the stream and
(2) the vertex arrival setting, where vertices on one side of the graph arrive
in the stream together with all their incident edges. The latter setting has
also been studied extensively in the context of online algorithms, where each
arriving vertex has to either be matched irrevocably or discarded upon arrival.
In the online setting, the celebrated algorithm of Karp-Vazirani-Vazirani
achieves a $1-1/e$ approximation. Despite the fact that the streaming model is
less restrictive in that the algorithm is not constrained to match vertices
irrevocably upon arrival, the best known approximation in the streaming model
with vertex arrivals and $\tilde O(n)$ space is the same factor of $1-1/e$.
  We show that no single pass streaming algorithm that uses $\tilde O(n)$ space
can achieve a better than $1-1/e$ approximation to maximum matching, even in
the vertex arrival setting. This leads to the striking conclusion that no
single pass streaming algorithm can do better than online algorithms unless it
uses significantly more than $\tilde O(n)$ space. Additionally, our bound
yields the best known impossibility result for approximating matchings in the
edge arrival model.
  We also give a simple algorithm that achieves approximation ratio
$1-e^{-k}k^{k-1}/(k-1)!=1-\frac1{\sqrt{2\pi k}}+o(1/k)$ in $k$ passes in the
vertex arrival model using linear space, improving upon previously best known
convergence.
