White‑Box Adversarial Streaming Lower Bounds beyond Two‑Party Communication

Streaming algorithms in adversarial settings have attracted considerable attention recently. We show that, in the white-box adversarial streaming model [ABJ+22], the fundamental problem of estimating the F_p moment to within any constant factor requires Ω(n) memory. In this model, the internal state of the (randomized) streaming algorithm is visible to an adversary, who can exploit this information when constructing subsequent stream updates. As a corollary, we also obtain a white-box lower bound for the well-studied problem of estimating the maximum matching size in graphs. 

[ABJ+22] proved that two-party white-box communication protocols can be derandomized. This allows them to prove deterministic communication lower bounds and automatically derive white-box (communication and streaming) lower bounds. However, such two-party lower bounds can only rule out approximation of the F_p moment within a specific constant factor. Ruling out approximation within any constant factor typically requires proving a lower bound for a multi-party communication problem.

We show that white-box communication protocols involving any number of parties can be derandomized, provided they compute a total function. However, this derandomization fails entirely when extended to partial functions and, consequently, to approximation problems. We are therefore compelled to prove our moment estimation lower bound for the white-box model directly. Our proof introduces a novel hybrid technique that, instead of taking hybrids over input distributions, constructs hybrids over white-box adversaries.