Proof settles the memory needed for streaming set cover
A mathematical proof shows that existing algorithms achieve the best possible tradeoff between computer memory, passes over data, and solution quality.
Edited by Boris Djordjevic · Paperfoot
In a preprint, researchers proved a mathematical limit on the memory needed to solve the set cover problem when data arrives in a stream. In this problem, an algorithm inspects collections of items arriving one by one and must find the fewest collections needed to cover every item, using only a few passes over the data and storing far less than the full stream.
The proof establishes a lower bound—a limit no algorithm can beat—relating memory, the number of passes, and how close the answer is to the true minimum. The authors showed this tradeoff matches what earlier algorithms achieved, up to constant and logarithmic factors. The proof relies on a randomized reduction from pointer chasing, a standard problem in communication complexity.
Why it matters
The result settles a decade-long open question in theoretical computer science by proving why progress on this problem had stalled. It shows that no algorithm can beat the established balance between memory, passes over data, and accuracy.
Caveats
The tight match between the lower bound and prior algorithms holds when the approximation factor is at least the number of passes, and the work is a preprint that has not yet been peer-reviewed.
In this paper
streaming set cover
What it shows
- Any α-approximation algorithm for streaming set cover requires Ω(m/α · (n/α)^(1/p)) space in p passes whenever α ≪ n^(1/(p+1)).
We provide a simple explanation for this lack of progress by establishing an optimal three-way space-pass-approximation tradeoff for this problem: any α-approximation algorithm for streaming set cover requires Ω(m/α · (n/α)^(1/p)) space in p passes whenever α ≪ n^(1/(p+1)).
Abstract
- Any log n or poly log(n)-approximation algorithm for streaming set cover requires Ω̃(mn^(1/p)) space in p passes.
We settle the conjecture of by proving that any \log{n} or even \mbox{\rm poly} \log {(n)} -approximation algorithm for streaming set cover requires \widetilde{\Omega}(mn^{1/p}) space in p -passes.
1.1 Our Contributions
- Theorem 1 generalizes the single-pass lower bounds by proving an Ω(mn/α^2) space lower bound for all choices of p ≪ log n.
Theorem 1 generalizes the single-pass lower bounds of who proved an \Omega(mn/\alpha^{2}) space lower bound (matching our tradeoff for p=1 ) to all choices of p\ll\log{n}.
Theorem 1.
- Theorem 1 generalizes multi-pass lower bounds by establishing that Ω(m) space is needed for (n/log n)^(1/(p+1)) approximation.
Theorem 1 also generalizes the multi-pass lower bounds of by proving that \Omega(m) space is needed for (n/\log{n})^{1/(p+1)} approximation, improving upon their \Omega(m^{1/p}) space lower bound (at a cost of a (\log{n})^{1/(p+1)} loss in our approximation ratio).
Theorem 1.
- A streaming algorithm using p passes and s space can be simulated by p+1 players using (p+1)·p·s total communication and p rounds.
Algorithm \mathcal{A} that uses p -passes and s space can be run by the (p+1) players using total communcation (p+1)\cdot p\cdot s total communication and p rounds.
Claim 3.6.
Quoted word for word from the full text on arXiv.
The paper
Settling the Pass Complexity of Streaming Set Cover
arXiv, Oct 1, 2026, Open access, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2610.01007
arXiv:2610.01007v1 in cs.DS
Comments: 25 pages, 4 figures; Full version appeared in STOC 2026
Cite as BibTeX
@misc{assadi2026settling,
title = {Settling the Pass Complexity of Streaming Set Cover},
author = {Assadi, Sepehr and Sundaresan, Janani},
year = {2026},
eprint = {2610.01007},
archivePrefix = {arXiv},
primaryClass = {cs.DS},
doi = {10.48550/arxiv.2610.01007},
url = {https://arxiv.org/abs/2610.01007}
}
