Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > WHITE-BOX STREAMING:
Reports tagged with White-box streaming:
TR26-060 | 22nd April 2026
Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

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 $\Omega(n)$ memory. In this model, the internal state of the (randomized) streaming algorithm is visible to ... more >>>




ISSN 1433-8092 | Imprint