Abstract: We consider the problem of maintaining a large matching and a small vertex cover in a dynamically changing graph. Each update to the graph is either an edge deletion or an edge insertion. We give the first randomized data structure that simultaneously achieves a constant approximation factor and handles a sequence of $K$ updates in $K\cdot \operatorname{polylog}(n)$ time, where $n$ is the number of vertices in the graph. Previous data structures require a polynomial amount of computation per update.