" Separations and equivalences between turnstile streaming and linear sketching "
Eric Price (UT Austin)
Abstract: A longstanding observation, which was partially proven in
Li-Nguyen-Woodruff '14, is that any turnstile streaming algorithm can
be implemented as a linear sketch (the reverse is trivially true). We
study the relationship between turnstile streaming and linear
sketching algorithms in more detail, giving both new separations and
new equivalences between the two models.
It was shown in [LNW14] that, if a turnstile algorithm works for
arbitrarily long streams with arbitrarily large coordinates at
intermediate stages of the stream, then the turnstile algorithm is
equivalent to a linear sketch. We show separations of the opposite
form: if either the stream length or the maximum value of the stream
are substantially restricted, there exist problems where linear
sketching is exponentially harder than turnstile streaming.
A further limitation of the [LNW14] equivalence is that the turnstile
sketching algorithm is neither explicit nor uniform, but requires an
exponentially long advice string. We show how to remove this
limitation for deterministic streaming algorithms: we give an explicit
small-space algorithm that takes the streaming algorithm and computes
an equivalent module.
Based on joint work with John Kallaugher, mostly available at https://arxiv.org/abs/1905.