Please note: This seminar will take place in DC 1304 and online.
Huacheng Yu, Associate Professor
Department of Computer Science, Princeton University
Linear sketches underlie many space-efficient streaming algorithms: rather than storing a changing vector, they maintain a small collection of linear measurements. Is this approach essentially as powerful as any turnstile streaming algorithm? Prior work established an equivalence for extremely long streams, while other results showed exponential separations for streams of linear length. This leaves a natural question: what happens for polynomial-length streams?
We show that an S-bit turnstile algorithm that handles polynomial-length streams can be converted into a linear sketch with O(S) measurements and O(S) bits of space. The conversion preserves space up to a constant factor and transfers sketching lower bounds to polynomial-length streaming algorithms.
The talk will focus on the intuition behind the proof. We probe an arbitrary algorithm with random updates and condition on its memory path. Fourier analysis then identifies the linear information that survives repeated addition, while a bound on the number of independent large Fourier frequencies limits the number of measurements.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.