Separations and Equivalences Between Turnstile Streaming and Linear Sketching

Explore the distinctions and similarities between turnstile streaming and linear sketching algorithms in this 26-minute conference talk presented at an Association for Computing Machinery (ACM) event. Delve into streaming algorithms, models, and their limitations, examining the reduction requirements and stream conditions that impact algorithmic performance. Investigate separations between turnstile algorithms and linear sketching, with a focus on triangle counting in various scenarios, including bounded-degree, constant-degree, and insertion-only cases. Learn about the extension of insertion-only algorithms and the concept of separation constructivity. Conclude with insights into further research directions in this field of computational theory.

Intro
Streaming Algorithms
Streaming Models
Limitations on Equivalence
Our Results
Linear Sketching
Reduction Requirements
Stream Conditions
Separating Turnstile Algorithms and Linear Sketches
Bounded-Degree Triangle Counting
Constant-Degree Triangle Counting
Insertion-Only Triangle Counting
Extending the Insertion-Only Algorithm
Separation
Constructivity
Conclusion and Further Work