{"ID":2859937,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.04918","arxiv_id":"2510.04918","title":"A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams","abstract":"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 $M = ([n], \\mathsf{d})$. The goal is to estimate the diameter of this multiset, defined as $\\max\\{\\mathsf{d}(i,j) : x_i, x_j \u003e 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 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^{Ω(1/c)}$ space. Our lower bound relies on two conceptual contributions: (1) a new connection between dynamic streaming algorithms and linear sketches for {\\em scale-invariant} functions, a class that includes diameter estimation, and (2) a connection between linear sketches for diameter and the {\\em 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.","short_abstract":"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 s...","url_abs":"https://arxiv.org/abs/2510.04918","url_pdf":"https://arxiv.org/pdf/2510.04918v1","authors":"[\"Sanjeev Khanna\",\"Ashwin Padaki\",\"Krish Singal\",\"Erik Waingarten\"]","published":"2025-10-06T15:32:40Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\",\"cs.CG\"]","methods":"[]","has_code":false}