Deterministic Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent Set
cs.DS
Submitted: 2026-09-16
Updated: 2026-10-28
Comments: 25 pages, 1 figure
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study the canonical and problems in the one-pass edge-arrival graph streaming setting.
Terminology
Abstract
We study the canonical and problems in the one-pass edge-arrival graph streaming setting. Here, the edges of some input graph G = (V,E) are presented one at a time (possibly including deletions), before an algorithm needs to produce either a large clique or independent set at the end of the stream, with the focus being on space complexity. We are interested in finding β-approximate solutions, for any β at least 1. Previous work gave an algorithm using O tilde (n 2/β 2) bits of space, together with a corresponding Ω (n 2/β 2) two-party communication lower bound [Halldórsson et al., ICALP'12], seeming to resolve the problem. However, their algorithm crucially relies on randomness, and the best known deterministic algorithm remains a folklore derandomisation using O (n 2/β) bits of space, leaving a (deterministic) gap of size O tilde(β). We make progress towards this gap with a strong lower bound for a restricted range of β: whenever β at most sqrt n /36 n, any deterministic algorithm for either problem must use Ω (n squared over β times n) bits of space. Our proof is via a two-party one-way communication lower bound, and highlights the power of randomness when approaching either of these problems.
Sources
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time