On the Deterministic Complexity of Counting Events in a Stream
summary
Deterministic algorithms that give a constant (2x) multiplicative approximation for counting ones in an insertion-only stream require sublinear but polynomial space: the proof gives an Omega(n^{1/3}) space lower bound for oblivious leveled branching programs (non‑uniform OBDDs). The argument builds maximal-intervals of reachable counts, tracks disappearing left-endpoint counts, and uses a containment lemma plus pigeonhole to force many intervals in one layer; the bound is combinatorial and constructive rather than information‑theoretic.
AI-written summary · about