  In the semi-streaming model, an algorithm receives a stream of edges of a
graph in arbitrary order and uses a memory of size $O(n \mbox{ polylog } n)$,
where $n$ is the number of vertices of a graph. In this work, we present
semi-streaming algorithms that perform one or two passes over the input stream
for maximum matching with no restrictions on the input graph, and for the
important special case of bipartite graphs that we refer to as maximum
bipartite matching (MBM). The Greedy matching algorithm performs one pass over
the input and outputs a $1/2$ approximation. Whether there is a better one-pass
algorithm has been an open question since the appearance of the first paper on
streaming algorithms for matching problems in 2005 [Feigenbaum et al., SODA
2005]. We make the following progress on this problem:
  In the one-pass setting, we show that there is a deterministic semi-streaming
algorithm for MBM with expected approximation factor $1/2+0.005$, assuming that
edges arrive one by one in (uniform) random order. We extend this algorithm to
general graphs, and we obtain a $1/2+0.003$ approximation.
  In the two-pass setting, we do not require the random arrival order
assumption (the edge stream is in arbitrary order). We present a simple
randomized two-pass semi-streaming algorithm for MBM with expected
approximation factor $1/2 + 0.019$. Furthermore, we discuss a more involved
deterministic two-pass semi-streaming algorithm for MBM with approximation
factor $1/2 + 0.019$ and a generalization of this algorithm to general graphs
with approximation factor $1/2 + 0.0071$.
