  We present a new approach for finding matchings in dense graphs by building
on Szemer\'edi's celebrated Regularity Lemma. This allows us to obtain
non-trivial albeit slight improvements over longstanding bounds for matchings
in streaming and dynamic graphs. In particular, we establish the following
results for $n$-vertex graphs:
  * A deterministic single-pass streaming algorithm that finds
  a $(1-o(1))$-approximate matching in $o(n^2)$ bits of space. This constitutes
the first single-pass algorithm for this problem in sublinear space that
improves over the $\frac{1}{2}$-approximation of the greedy algorithm.
  * A randomized fully dynamic algorithm that with high probability maintains a
$(1-o(1))$-approximate matching in $o(n)$ worst-case update time per each edge
insertion or deletion. The algorithm works even against an adaptive adversary.
This is the first $o(n)$ update-time dynamic algorithm with approximation
guarantee arbitrarily close to one.
  Given the use of regularity lemma, the improvement obtained by our algorithms
over trivial bounds is only by some $(\log^*{n})^{\Theta(1)}$ factor.
Nevertheless, in each case, they show that the ``right'' answer to the problem
is not what is dictated by the previous bounds.
  Finally, in the streaming model, we also present a randomized
$(1-o(1))$-approximation algorithm whose space can be upper bounded by the
density of certain Ruzsa-Szemer\'edi (RS) graphs. While RS graphs by now have
been used extensively to prove streaming lower bounds, ours is the first to use
them as an upper bound tool for designing improved streaming algorithms.
