Answers are grounded in this paper and cite their sources.
We design adversarially robust algorithms for dynamic geometric streams that $(1 + ε)$-approximate k-Median and k-Means in Euclidean space Rᵈ, using Õ(kd poly(ε⁻¹)) space. This result significantly improves a recent O(dlog n)-approximation for k-Median [Gribelyuk, Lin, Woodruff, Yu, and Zhou, FOCS 2026], and is furthermore the first algorithm whose space is linear in $kd$, even in the oblivious (non-adaptive) setting. We develop several new techniques which may be of independent interest, including a new data-oblivious Euclidean primitive called hierarchical Lipschitz assignment, a robust dimensionality reduction for clustering, and a robust streaming algorithm for inner-product queries.
No takes yet. Share an insight, caveat, or question.
Guo et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: