Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > STREAMING LOWER BOUNDS:
Reports tagged with Streaming lower bounds:
TR23-003 | 11th January 2023
Shachar Lovett, Jiapeng Zhang

Streaming Lower Bounds and Asymmetric Set-Disjointness

Frequency estimation in data streams is one of the classical problems in streaming algorithms. Following much research, there are now almost matching upper and lower bounds for the trade-off needed between the number of samples and the space complexity of the algorithm, when the data streams are adversarial. However, in ... more >>>


TR24-067 | 10th April 2024
Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang

Breaking Square-Root Loss Barriers via Min-Entropy

Information complexity is one of the most powerful tools to prove information-theoretical lower bounds, with broad applications in communication complexity and streaming algorithms. A core notion in information complexity analysis is the Shannon entropy. Though it has some convenient properties, such as chain rules, Shannon entropy still has inherent limitations. ... more >>>


TR25-148 | 12th October 2025
Noah Singer

Nine lower bound conjectures on streaming approximation algorithms for CSPs

In this column, we overview recent progress by many authors on understanding the approximability of constraint satisfaction problems (CSPs) in low-space streaming models. Inspired by this recent progress, we collate nine conjectural lower bounds against streaming algorithms for CSPs, some of which appear here for the first time.

more >>>



ISSN 1433-8092 | Imprint