Exponential Separations Between Turnstile Streaming and Linear Sketching

05/07/2019

∙

by   John Kallaugher, et al.

∙

0

∙

share

Almost every known turnstile streaming algorithm is implementable as a linear sketch. Is this necessarily true, or can there exist turnstile streaming algorithms that use much less space than any linear sketch? 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 can be implemented as a linear sketch. Our results have 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.