Appears in collection : 2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

I will cover recent developments in characterizing the space-optimal turnstile data stream algorithm for computing any relation of an underlying frequency vector as a linear sketch. I'll first discuss the original proof of this result, then several optimizations which have applications to obtaining optimal lower bounds for counting with additive error, dynamic graph matching, and frequency moments, which we do not know how to prove in another way. I'll also mention multi-pass extensions. Based on joint works with Yuqing Ai, Wei Hu, Yi Li, Huy Nguyen, and Omri Weinstein