Continuous monitoring of ${\ell }_p$ norms in data streams

Jarosław Błasiok, Jian Ding, Jelani Nelson

In insertion-only streaming, one sees a sequence of indices $a_1,a_2,\dots ,a_m\in [n]$. The stream defines a sequence of $m$ frequency vectors $x^{(1)},\ldots,x^{(m)}\in\mathbb…