High Probability Streaming Lower Bounds for $F_2$ Estimation

William Swartworth, David P. Woodruff, Samson Zhou

Estimating the second frequency moment ($F_2$) of an underlying frequency vector is a fundamental problem in the streaming model. While recent work by Braverman and Zamir [STOC 202…