  In this paper, we introduce a new model for sublinear algorithms called
\emph{dynamic sketching}. In this model, the underlying data is partitioned
into a large \emph{static} part and a small \emph{dynamic} part and the goal is
to compute a summary of the static part (i.e, a \emph{sketch}) such that given
any \emph{update} for the dynamic part, one can combine it with the sketch to
compute a given function. We say that a sketch is \emph{compact} if its size is
bounded by a polynomial function of the length of the dynamic data,
(essentially) independent of the size of the static part.
  A graph optimization problem $P$ in this model is defined as follows. The
input is a graph $G(V,E)$ and a set $T \subseteq V$ of $k$ terminals; the edges
between the terminals are the dynamic part and the other edges in $G$ are the
static part. The goal is to summarize the graph $G$ into a compact sketch (of
size poly$(k)$) such that given any set $Q$ of edges between the terminals, one
can answer the problem $P$ for the graph obtained by inserting all edges in $Q$
to $G$, using only the sketch.
  We study the fundamental problem of computing a maximum matching and prove
tight bounds on the sketch size. In particular, we show that there exists a
(compact) dynamic sketch of size $O(k^2)$ for the matching problem and any such
sketch has to be of size $\Omega(k^2)$. Our sketch for matchings can be further
used to derive compact dynamic sketches for other fundamental graph problems
involving cuts and connectivities. Interestingly, our sketch for matchings can
also be used to give an elementary construction of a \emph{cut-preserving
vertex sparsifier} with space $O(kC^2)$ for $k$-terminal graphs; here $C$ is
the total capacity of the edges incident on the terminals. Additionally, we
give an improved lower bound (in terms of $C$) of $\Omega(C/\log{C})$ on size
of cut-preserving vertex sparsifiers.
