A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams

We study the space complexity of estimating the diameter of a subset of points in an arbitrary metric space in the dynamic (turnstile) streaming model. The input is given as a stream of updates to a frequency vector $x \in \mathbb{Z}_{\geq 0}^{n}$, where the support of x defines a multiset of points in a fixed metric space $\mathcal{M}=([n], \mathrm{d})$. The goal is to estimate the diameter of this multiset, defined as max $\left\{\mathrm{d}(i, j): x_{i}, x_{j} \gt \right. 0\}$, to a specified approximation factor while using as little space as possible. In insertion-only streams, a simple $O(\log n)$-space algorithm achieves a $\mathbf{2}$-approximation. In sharp contrast to this, we show that in the dynamic streaming model, any algorithm achieving a constant-factor approximation to diameter requires polynomial space. Specifically, we prove that a c-approximation to the diameter requires $n^{\Omega(1 / c)}$ space. Our lower bound relies on two conceptual contributions: (1) a new connection between dynamic streaming algorithms and linear sketches for scale-invariant functions, a class that includes diameter estimation, and (2) a connection between linear sketches for diameter and the minrank of graphs, a notion previously studied in index coding. We complement our lower bound with a nearly matching upper bound, which gives a c-approximation to the diameter in general metrics using $n^{O(1 / c)}$ space.