Problem 64: Matchings in the Turnstile Model

Suggested by	Andrew McGregor
Source	Bertinoro 2014
Short link	https://sublinear.info/64

Suppose we are in a turnstile model for graph streaming: this means that the stream consists of a sequence of edge insertions and deletions (with no edge being deleted before it's inserted). In this setting, can we design an algorithm for computing a matching that takes space $o(n^2)$ and gets a constant approximation (or better ) ?