BARC talk by John Kallaugher
Tuesday, 9 July, John Kallaugher, PhD student, Department of Computer Science at UT Austin, will give a talk "Exponential Separations Between Turnstile Streaming and Linear Sketching"
Title:
Exponential Separations Between Turnstile Streaming and Linear Sketching
Abstract:
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~\cite{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.
https://arxiv.org/abs/1905.02358
Bio:
John Kallaugher is PhD student in the Department of Computer Science at UT Austin. His advisor is Eric Price. Read more about John Kallaugher here.