{"ID":22952785,"CreatedAt":"2026-09-17T02:12:05.498442134Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19089","arxiv_id":"2609.19089","title":"A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic Streams","abstract":"We study the space complexity of diameter estimation for a set of points in Euclidean space in the dynamic (turnstile) streaming model. The seminal work of Indyk (SODA 2003) gives a $c$-approximation to the Euclidean diameter of $n$ vectors using $n^{O(1/c^2)}$ space. Our main contribution is giving an essentially matching lower bound. Any dynamic streaming algorithm which can $c$-approximate the diameter of $n$ Euclidean vectors must use $n^{\\tildeΩ(1/c^2)}$ space.","short_abstract":"We study the space complexity of diameter estimation for a set of points in Euclidean space in the dynamic (turnstile) streaming model. The seminal work of Indyk (SODA 2003) gives a $c$-approximation to the Euclidean diameter of $n$ vectors using $n^{O(1/c^2)}$ space. Our main contribution is giving an essentially matc...","url_abs":"https://arxiv.org/abs/2609.19089","url_pdf":"https://arxiv.org/pdf/2609.19089v1","authors":"[\"Ashwin Padaki\",\"Krish Singal\",\"Erik Waingarten\"]","published":"2026-09-16T17:26:50Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CG\"]","methods":"[]","has_code":false}