Deterministic Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent Set

arXiv:2609.18635 · cs.DS · Submitted 2026-09-16 · Read on arXiv

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