Why psuedorandomness is important in frequency moment estimation

from blog Alex Clemmer, | ↗ original
Finding the \( p \)-th frequency moment, denoted \( F_p \), is one of the most well-studied problems in streaming algorithms, with a broad set of applications ranging from traffic monitoring on networks, to efficient entropy estimation, to database query optimization. In the streaming setting, this task amounts to computing \( F_p(\mathbf{x}) =...