BIU theory seminar- June 7 : Shachar Lovett (UCSD) - Streaming Lower Bounds and Asymmetric Set-Disjointness

[Arnold Filtser]

Hello all,

Next week (Wed June 7, at 12) we will meet for our theory seminar.

Location: Building 605 room 14.

See you there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Shachar Lovett (UCSD)

Title: Streaming Lower Bounds and Asymmetric Set-Disjointness
Abstract: Streaming algorithms are widely studied in theory and used in practice. Space efficient algorithms have been developed for many fundamental problems (such as counting the number of unique elements in a stream, finding heavy hitters, etc). These algorithms are known to be optimal against worst case streams, where the lower bound techniques leverage lower bounds in communication complexity; concretely, for the unique set disjointness problem.

In recent years, there has been a shift towards average case analysis, where streams are assumed to be random in some way. This does not seem to help many of the existing algorithms, but the lower bound techniques break down. This leaves open the question of whether streaming algorithms can be improved for random streams.

In this work, we extend the lower bounds to random streams, thus showing that existing algorithms are optimal even for random streams. Technically, it leverages a new lower bound for an asymmetric version of the unique set disjointness problem.

Based on joint work with Jiapeng Zhang

[Arnold Filtser]

The seminar starts in one hour!