Algorithms and Complexity Seminar

Revisiting Norm Estimation in Data Streams

Jelani Nelson (MIT)

The problem of estimating the pth moment Fp (p nonnegative and real) in a data stream is as follows. There is a vector x which starts as 0, and many updates of the form xi ← xi + v come sequentially in a stream (v can be negative). The algorithm also receives an error parameter 0 < ε < 1. The goal is to output an approximation with relative error ε to Fp = ||x||pp.

Previously, it was known that polylogarithmic space (in the vector length n) was achievable if and only if p ≤ 2. We make several new contributions in this regime, including: As corollaries of our work, we discover a few separations in complexity: F0 in 1 pass vs. 2 passes, p = 0 vs. p > 0, and F0 with strictly positive updates vs. arbitrary updates.

Joint work with Daniel Kane (Harvard) and David Woodruff (IBM Almaden).