BARC talk by John Kallaugher – University of Copenhagen

BARC > Events > BARC talk by John Kall...

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.