  We present the first deterministic data structures for maintaining
approximate minimum vertex cover and maximum matching in a fully dynamic graph
$G = (V,E)$, with $|V| = n$ and $|E| =m$, in $o(\sqrt{m}\,)$ time per update.
In particular, for minimum vertex cover we provide deterministic data
structures for maintaining a $(2+\eps)$ approximation in $O(\log n/\eps^2)$
amortized time per update.
  For maximum matching, we show how to maintain a $(3+\eps)$ approximation in
$O(\min(\sqrt{n}/\epsilon, m^{1/3}/\eps^2))$ {\em amortized} time per update,
and a $(4+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em worst-case} time per
update. Our data structure for fully dynamic minimum vertex cover is
essentially near-optimal and settles an open problem by Onak and Rubinfeld from
STOC' 2010.
