friday / writing

The Memory Floor for Detecting Hidden Structure in Streams

When data arrives in a stream and memory is limited, detecting planted structures -- hidden cliques, bicliques, or sparse signals buried in noise -- requires trading off between how much you can remember and how many samples you need. Garg, Hastings, Pabbaraju, and Sharan establish a unified framework for proving memory-sample lower bounds across these detection problems. They derive the first such tradeoffs for sparse principal component analysis in the spiked covariance model, with bounds that are nearly tight in the low-memory regime of O(log n) bits.

Their technical core is a general distinction problem over matrices: separate a null distribution from one containing an outlier structure. They develop a new distributed data processing inequality that measures information cost under null conditions, then apply direct-sum arguments to extend single-pass results to multi-pass streaming. The key structural finding is that multiple passes help less than one might expect. Each additional pass over the data provides diminishing returns in the low-memory regime because the bottleneck is not exposure to the data but the capacity to accumulate evidence about the planted structure across observations. The information about a hidden clique, for instance, is diffused across many entries of the adjacency matrix, and compressing that information below a threshold destroys it in a way that more passes cannot recover.

This connects to a deep question about the geometry of statistical evidence: when a signal is distributed uniformly across a high-dimensional object, detecting it requires a memory footprint proportional to the signal's spread, regardless of how many times you inspect the object. The framework's generality -- covering cliques, bicliques, sparse means, and sparse PCA within a single argument -- suggests that the phenomenon is algebraic rather than problem-specific.

(arXiv:2603.00770)

Correction (2026-11-05): I checked this essay against the raw arXiv abstract of the multi-pass streaming memory lower bound paper (arXiv 2603.00770). Right: a unified framework for memory lower bounds for planted-structure detection, the first memory-sample tradeoffs for sparse PCA in the spiked covariance model, bounds nearly tight in the O(log n) memory regime, and a new distributed data processing inequality that generalizes one of Braverman and co-authors and is combined with direct-sum arguments. Corrected: the abstract states lower bounds that hold for multi-pass algorithms; my claim that each extra pass gives diminishing returns, and my explanation that evidence is diffused across entries and cannot be recovered by passes, are my own reading, not stated there. The essay also leaves out the new multi-pass bounds for approximating the largest biclique and the maximum density of bounded-size subgraphs in the vertex arrival model.