Lune

NeurIPS2025Top-tier venue

Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond

Kiarash Banihashem, Jeff Giliberti, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh

Abstract

In this paper, we study the fundamental problems of maintaining the diameter and a kk-center clustering of a dynamic point set P⊂RdP \subset \mathbb{R}^d, where points may be inserted or deleted over time and the ambient dimension dd is not constant and may be high. Our focus is on designing algorithms that remain effective even in the presence of an adaptive adversary -- an adversary that, at any time tt, knows the entire history of the algorithm's outputs as well as all the random bits used by the algorithm up to that point. We present a fully dynamic algorithm that maintains a 22-approximate diameter with a worst-case update time of poly(d,log⁡n)\text{poly}(d, \log n), where nn is the length of the stream. Our result is achieved by identifying a robust representative of the dataset that requires infrequent updates, combined with a careful deamortization. To the best of our knowledge, this is the first efficient fully-dynamic algorithm for diameter in high dimensions that simultaneously achieves a 2-approximation guarantee and robustness against an adaptive adversary. We also give an improved dynamic (4+ϵ)(4+\epsilon)-approximation algorithm for the kk-center problem, also resilient to an adaptive adversary. Our clustering algorithm achieves an amortized update time of k2.5d⋅poly(ϵ−1,log⁡n)k^{2.5} d \cdot \text{poly}(\epsilon^{-1}, \log n), improving upon the amortized update time of k6d⋅poly(ϵ−1,log⁡n)k^6 d \cdot \text{poly}(\epsilon^{-1}, \log n) by Biabani et al. [NeurIPS'24].

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Adversarially Robust Approximate Furthest Neighbor cites Adversarially Robust Streaming Algorithms via Differential Privacy
  • Adversarially Robust Approximate Furthest Neighbor cites On Adaptive Distance Estimation
  • Adversarially Robust Approximate Furthest Neighbor cites On the Robustness of CountSketch to Adaptive Inputs
  • Adversarially Robust Approximate Furthest Neighbor cites Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
  • On the Robustness of CountSketch to Adaptive Inputs cites Adversarially Robust Streaming Algorithms via Differential Privacy
  • On the Robustness of CountSketch to Adaptive Inputs cites Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Adversarially Robust Approximate Furthest NeighborKiarash Banihashem, Jeff Michael Giliberti, Prashant Gokhale, Samira Goudarzi et al.ICML 2026

Builds on23

  1. Adversarially Robust Streaming Algorithms via Differential PrivacyAvinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias et al.NeurIPS 2020 · 85 citations
  2. On Adaptive Distance EstimationYeshwanth Cherapanamjeri, Jelani NelsonNeurIPS 2020 · 34 citations
  3. On the Robustness of CountSketch to Adaptive InputsEdith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós et al.ICML 2022 · 29 citations
  4. Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference EstimatorsDavid P. Woodruff, Samson ZhouFOCS 2021 · 25 citations
  5. New algorithms and hardness for incremental single-source shortest paths in directed graphsMaximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole WeinSTOC 2020 · 21 citations

Related papers

  1. Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious AdversariesMohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger et al.SODA 2023 · 11 citations
  2. Fully Dynamic Consistent k-Center ClusteringJakub Lacki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram et al.SODA 2024 · 5 citations
  3. Dynamic Consistent k-Center Clustering with Optimal RecourseSebastian Forster, Antonis SkarlatosSODA 2025 · 2 citations
  4. Dynamic algorithms for k-center on graphsEmilio Cruciani, Sebastian Forster, Gramoz Goranci, Yasamin Nazari et al.SODA 2024 · 4 citations
  5. Almost Optimal Fully Dynamic k-Center Clustering with RecourseSayan Bhattacharya, Martín Costa, Ermiya Farokhnejad, Silvio Lattanzi et al.ICML 2025
Dusk over the sea between two cliffs drawn in fine vertical lines