Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
Authors: Kiarash Banihashem
Jeff Giliberti
Samira Goudarzi
MohammadTaghi Hajiaghayi
Peyman Jabbarzade
Morteza Monemizadeh
Venue: NeurIPS 2025 poster ()
Keywords: Dynamic algorithm
diameter problem
adaptive adversary
high dimensional space
Primary area: theory

Abstract: In this paper, we study the fundamental problems of maintaining the diameter and a $k$-center clustering of a dynamic point set $P \subset \mathbb{R}^d$, where points may be inserted or deleted over time and the ambient dimension $d$ is not constant and may be high. Our focus is on designing algorithms that remain effective even in the presence of an \emph{adaptive adversary}—an adversary that, at any time $t$, 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 $2$-approximate diameter with a \emph{worst-case} update time of $poly(d, \log n)$, where $n$ 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 \emph{simultaneously} achieves a $2$-approximation guarantee and robustness against an adaptive adversary. We also give an improved dynamic $(4+\epsilon)$-approximation algorithm for the $k$-center problem, also resilient to an adaptive adversary. Our clustering algorithm achieves an amortized update time of $k^{2.5} d \cdot poly(\epsilon^{-1}, \log n)$, improving upon the amortized update time of $k^6 d \cdot poly( \epsilon^{-1}, \log n)$ by Biabani et al. [NeurIPS'24].

Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond*
Kiarash Banihashemi University of Maryland College Park, MD, USA kiarash@umd edu
Jeff Gilibertit University of Maryland College Park, MD, USA jeffgi Seffgill@uudd @umd edu
Samira Goudarzi University of Maryland College Park, MD, USA samiragoumd. edu
Mohammad Taghi Hajiaghayil University of Maryland College Park, MD, USA haj majiagha@umd. edu
Peyman Jabbarzade" University of Maryland College Park, MD, USA peyman @@udd. edu
Morteza Monemizadeh' TU Eindhoven Eindhoven, The Netherlands M. w.M.onmizadeh@tuue nl
Abstract
In this paper, we study the fundamental problems of maintaining the diameter and k-center clustering of dynamic point set P C Rdd where points may be inserted or deleted over time and the ambient dimension is not constant and may be high. in the presence of
Our focus is on designing algorithms that remain effective an adaptive adversary-an adversary that, at any time t, knows the entire history of the algorithm's 's outputs well all the random bits used by the algorithm up to that point. We present fully dynamic algorithm that maintains a 2-approximate diameter with a worst-case update time poly (d, log n),, where of the stream. Our result is achieved by identifying a robust representative of the dataset that requires infrequent updates, combined with careful deamortization. To the best of our knowledge, this is the first efficient fully-dynamic algorithm for diameter in high dimensions that simultaneously achieves 2- 2-approximation guarantee and robustness against an adaptive adversary. We also give an improved dynamic (4 + e)-approxination algorithm for the k-center problem, also resilient to an adaptive adversary. Our clustering algorithm achieves an amortized update time of k2.5d poly(e log n).. improving upon the amortized update time k poly(e- logn) by Biabani et al. [NeurIPS"24]
the length
1 Introduction
Maintaining representative propertics dynamic point set, such as its current diameter and k-center clusters, a fundamental computing task. Given set of points P in d-dimensional Euclidean space, with P subject to insertions and delctions, our goal is to efficiently compute and maintain approximate diameter, minimum enclosing ball and k-center clustering. We interested in algorithms that robust against an adaptive adversary, that is, the algorithm performance is evaluated against an instance that adapts to the previous choices of the algorithm.
Approximating the diameter of a dataset-thh the greatest pairwise distance-iss a fundamental geometric operation with direct relevance to machine learning. It is commonly used in clustering to measure
'The work is partially supported by DARPA QuICC, ONR MURI 2024 award on Algorithms, Learning, and Game Theory, Aemy-Research Lahoratory (ARL) grant W91 10022 NSF AF:Small grants 2218678 14269, 2347322. EEual Contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

the spread of a cluster, where smaller diameter indicates that data points within a cluster are more similar to each other. In hierarchical clustering algorithms, diameter thresholds are often used to determine whether clusters should be merged or split (Liu et al. 2012]. In outlier detection, points that substantially increase the diameter of dataset can be flagged as anomalies [Aggarwal 2016]. Diameter also arises in approximate furthest neighbor queries (Pagh et al.] 2015] and in active learning, where it quantifies the uncertainty over hypotheses [Tosh and Dasgupta 2017]. These applications become particularly challenging in high-dimensionn computation is expensive and geometric properties often degrade [Indyk] 2000 Goel et al. [00T]] making standard restancee-asee methods less effective and harder to analyze [Indyk and Motwani 1998 Har-Peled et al., 2012].
settings, where exact diameter
Minimum Enclosing Ball (MEB) is closely related to diameter and plays a central role in high- dimensional data analysis, particularly in one-class SVMs [Tax and Duin, 2004) and Support Vector Data Description (SVDD) [Frandi et al. 2010]. A MEB captures the spread of the data by enclosing it in the smallest possible hypersphere, whose center and radius define the classifier's parameters and decision boundary. In dual SVM formulations, solving the MEB corresponds to identifying support vectors that lie on the boundary of the ball. Fast and efficient MEB computation is thus crucial for scaling SVM training to large, high-dimensional datasets [Baooi and Clarkson 2003 Clarkson
2010 Clarkson et al. 2012]. where the cost of exact geometric operations can become a bottleneck.
Diameter Problem. Designing dynamic algorithms for approximating the diameter of a point set in Euclidean space is particularly challenging when facing an adaptive adversary one that reacts to the algorithm's s internal randommess or past outputs. A folklore (dynamic) 2-approximation algorithm (e.g.. Chan and Pathak (2014) picks random anchor point p E P and maintains its furthest neighbor throughout updates. This strategy has O(dlog r)) amortized update time, since the anchor is deleted with probability 1/me for n -Pl-
However, the algorithm is fragile: if the adversary deletes p. the guarantee fails, and the procedure must be restarted- pooentied requiring (n) time. Surprisingly, the update time of this is simple and vulnerable method remains the best known when faced with an adaptive adversary. Developing a robust, fully dynamic algorithm with any non-trivial approximation that has worst-case poly (d log n) update time remains an important open problem. We summarize existing bounds in Table
Approximation
Update Time
Guarantee
Adversary
Algorithm
2
Od
Amortized
Oblivious
Folklore
1+e
(dd-2/(1+e)") -a(d)
Worst-case
Oblivious
Indyk
2003
1 1+c
Worst-case
Deterministic
Zarrabi-Zadeh
201
V2+ +
(dg
Amortized
Oblivious
CCan and Pathak
2014
2
Old log" n)
Worst-case
Adaptive
This paper
Table 1: State-of-the-art algorithms for fully-dynamie diameter.
k-Center Clustering. The k-center problem seeks is representative points that minimize the maxi- mum distance to any point in the dataset, and is a well-studied objective in clustering. In the static setting, a simple greedy algorithm achieves a 2-approximation [Gonzalez] 1985 Hochbaum and Shmoys 1986), which is NP-hard to improve for any constant factor Hss and Nemhauser 1979| in
Euclidean spaces, this can be refined 1.822 [Feder and Greene 1988 Bern and Eppstein 1997.
Dynamic variants of k-center clustering have attracted significant interest (e.g., Charikar et al. 1997
Chan et al. [2018]. [Btenn et al. [2023], |ąçci et al.) (2024)), with a focus on balancing approxi- mation quality, update time, and robustness. Similar to the diameter problem, key performance measures include: (1) the approximation ratio; (2) per-update time (amortized or worst-case); and (3)
resilience to different adversary models (oblivious. adaptive, or deterministic). Table 2) summarizes the statc-of-the across these dimensions; see scc|Appendix A for additional discussion.
Despite recent advances, the complexity of fully dynamic k-center clustering against an adaptive adversary remains poorly understood. In particular, there is significant gap between the nearly optimal approximation and update time guarantees in the oblivious setting [Bateni et al. 2023 and the recent (4 + 2)- approoxmmttio by (Biabani et al. 2024). which incurs an amortized update time of Õ(K9) prohibiiiily large even for small k. Sacrificing update time further, [Goranci et al. 2021 achieve 2 + approximation with update time exponential in d, which is practical only for small
2

---

Approximation
Update Time
Guarantee
Adversary
Algorithm
2+
20(4) 0(1)
Worst-case
Deterministic
Goranci et al.
202
2+6
(k/e))
Amortized
Oblivious
Bateni et
2023
log(n/k1) (min (ki 0(1)
loglog
Ō(k)
Amortized
Deterministic
Bateni et al.
2023
poly(n, k) O(k%)
Worst-case
Deterministic
F.acki et al.
2024
4+c
Amortized
Adaptive
Biabani et al.
2024
4
5(k255)
Amortized
Adaptive
This paper
Table 2: State-of-the-art algorithms for fully dynamic k-center clustering. The O(-) notation hides d and poly log(k; n, p. ) factors, where p denotes the spread ratio of the dataset. Our algorithm is for Euclidean spaces, while the other results are for general metric spaces. The algorithm of [Biabani ct al. 2024 is developed for k-center with outliers.
dimensions. More recently, Lacki et al. 2024). Forster and Skarlatos (2025 obtained deterministic 0(1) approxxpoonnn algorithms with polynomial update time n.
Adaptive adversary. Dynamic algorithms [Onak and Rubinfeld, 2010 Baswana et al. 2018
Abraham al.] 2016) have commonly assumed oblivious adversary, that is, the adversary must choose in advance an instance against which the algorithm evaluated. Unfortunately, it turns out that the assumption of an oblivious adversary is problematic in many natural scenarios. This is the case when a dynamic algorithm is used as a subroutine inside another algorithm, when a database update depends a previous one, or when the algorithm is faced with adversarial attacks.
In theoretical computer science and machine learning, several notions of adaptive adversary have been studied extensively. We consider an adaptive adversary who has full knowledge of the algorithm and can see its random choices up to that point, but not future ones. This a natural and a central notion of adversary: it is the strongest possible adversary against which randomized algorithm can be evaluated. The adversary is able to decide future updates based on the past decisions of the algorithm, and its updates might force the algorithm to misbehave, by either producing incorrect answer or taking a long time to run. This definition of adversary closely reflects the white-box adversarial model in robust machine learning [Ilyas et al., 2019 Madry al. 2018
In the white-box setting, an adversary has access to the internal structure of a machine learning model, including its parameters and training data, such as its parameters or training weights. This level of access makes the adversary particularly powerful: recent work has shown that even subtle input perturbations can mislead the model into making incorrect predictions (see [Biggio al. 2013 Athalye al., 2018 and references therein). As result, developing algorithms that are robust white-box ad veresaaia attacks has become central focus in robust machine learning [[lyas] cct al. 2019 Madry et al.) 2018 Tramèr et al. al.[2018 2018 Kurakin et al. 2017 Liu et al. 2017], as well as dynamic Nanongkai and Saranurak 2017 Cherapanamjeri and Nelson 2020 Wajc 2020].
streaming [Ben-eliezer and Yogev 2020 jtai et al. 2022], and other Big settings MMronov
et al. 2008 Boounovic al. 2017
The robustness of fully-dynamic algorithms against adaptive adversaries has recently received
significant attention [Nanongkai and Saranurak, [017]] Waje 2020, [ateni et al. [2223] Roghani al. 22022.. Similar notions have also been studied in the streaming model AAtai et al. 2022 Feng and Woodruff] 2023] Feng et al.) 2024]. We emphasize that our notion of adaptive adversary is
significantly stronger than the commonly studied model, where the adversary can observe the outputs of the algorithm over time but not its internal random choices. To distinguish the two, refer to stronger model as the cecllooness-ddaptii adversary and the weaker one as the output- output-adaptive adversary. This distinction parallels the difference between white-box and black-box adversarial attacks in machine learning.
A key distinction is that, under an output-adaptive adversary, one can often design algorithms that carefully manage dependencies between internal randomness and observable outputs, thus preventing information leakage. Such techniques, however, break apart when the adversary has visibility into the random choices themselves. For many problems-includiee including diameter and k-center clustering- the gap between output-adaptive and aiddomness--daaptin adversaries remains poorly understood.
3

---

1.1 Our Contribution
We design a fully-dynamic algorithm for approximating the diameter in high- sigh-dimessionll Euclidean spaces that is robust to an adaptive adversary. The same algorithm extends to maintaining a minimum enclosing ball (MEB) that encloses the given point set. Our main result is the following:
Theorem 1.1. For the diameter and minimum enclosing ball (or 1-center) problems in d dimensions, there exists sallly-yymaiic algorithm that achieves 2-approximatton with success probability at least 1 - 6. The algorithm works against a randomness-adapito
adversary and guarantees a worst-case update time of O(d log (dd) log logg-((1z (n/6)), where n is the length of the update stream.
Our algorithm is the first to be resilient against a randomness-adaue adaptive adversary, while achieving a non-trivial constant approximation in high dimensions. Previously, efficient algorithms were known only for small values of d (Zarrabi-Zadeh 2011].
We extend some techniques developed for the diameter problem the k-center clustering problem for k 2 2, resulting in the following result that improves the amortized update time k polly(d, loog of Biabani et al. 2024).
Theorem 1.2. Let l E N and 0 < < S 1. For the k-center problem in d dimensions, there exists a dully-dynamie algorithm that achieves a (4+
with success probability at least mundommess-adaptiin adversary and guarantees an amortized update time of 5.2.d poly(log n, e1 5), where a the length of the update stream.
1 - 6. The algorithm works against
Overview of our techniques. One of our main technical contributions is the development of algorithms that remain resilient to adversarial updates, even when the adversary has full knowledge of the current state of the algorithm. To withstand such an adversary, our algorithms cannot rely on random decisions; instead, their decisions must be provably robust. This requirement rules out many commonly used techniques in dynamic algorithms for achieving fast update times or black-box robustness. In particular, it eliminates the of random decisions CCan and Pathak [2014) (e.g.. an adversary deletes a randomly chosen point from P with probability 1/IP), as well as the use of differential privacy (Cherapanamjen et al., 2023 Hassidim al., [022] that includes reporting noisy answers and obfuscating the state of the algorithm through multiple copies with varying randomness.
Although our dynamic algorithms are randomized, randomness is used solely accelerate the decision-making process. This contrasts fundamentally with prior dynamic algorithms against oblivious adversaries [Indyk] 2003 Chan and Pathak [014 Bateni al. 2023), where randomness is typically used to make decisions that adversaries cannot exploit.
For both the diameter and k:-center problems, we quantify the robustness of "decision" by the number of updates it can withstand. Intuitively, a decision requiring O(T) time to compute considered e-robust if it remains valid after applying O(eT') changes to the underlying dataset, for some 0 < E << 1. Beyond O(e2') updates, the data may have changed significantly, making even a robust decision irrelevant. Thus, the algorithm must re-compute and establish new "robust" decision capable of withstanding the subsequent updates. Our dynamic diameter and k-center algorithms both rely on this iterative approach.
In the case of the diameter problem, we compute an e-robust representative point (Definition 2.2 that continues to be representative of the surviving point set (i.e., points that are inserted but not deleted the dynamic setting) even after (eTT) deletions. However, it is not immediately obvious whether such e-robust representatives exist or whether they can be computed efficiently. The core novelty of our framework lies in showing that such points can indeed be constructed and maintained efficiently. The construction step relies on the notion of centerpoint [Har-Peled and Jones 2020 Clarkson et al.) 1993 (see Definition 2.5). Informally, a centerpoint a point that lies "deep" within a point set. To our knowledge, this is the first application of centerpoints in dynamic algorithms, and we believe this technique has broader potential in developing dynamic and streaming algorithms resilient to adaptive adversaries.
For the k-center problem, the robustness of a cluster center is quantified by the number of nearby moints-those within some distance D. Since any point lies within distance at most OPT of an optimal center e", a previously opened center e that still retains a nearby point (within distance D) can cluster all points assigned to c* using radius D + 20PT. This idea is also used in prior work on

---

k-center clustering (Biabani et al. 2024 Cohen- Addad et al., 2016]. Our main contribution for this problem is a faster update time through more careful random sampling, which we overview below.
To find robust centers, we sample Ö(k) points and, for each sampled point, measure the fraction of other sampled points that lie within a ball of radius 2 -PT around it. This identifies a sampled point that is robust with respect to the sample in total time (k?)). This procedure is efficient when the number of clusters is relatively small. If k S 2/3 the above sampling and pairwise coverage tests suffice, giving overall cost of ((k2).
When k > 2/2 we reduce the sample size to Ö(Vk) and change the robustness test: rather than testing coverage among sampled points, we test for each sampled point the fraction of original points in P that lie within radius 2 OPT, incurring an overall cost of Ö(vk n)). Two scenarios now cover all possibilities. First, if the largest vi clusters each contain at least n points, then with high probability each such large cluster is represented in the sample; estimating robustness against the original dataset then finds robust centers from these clusters. Second, if the remaining k - v clusters together contain at most n/tt points for some constant & (e.g. t = 4), then the large clusters account for at least (1 1/ points and, by the pigeonhole principle, at least one large cluster must contain (n/ /k) points. Sampling Ö( kk) points uniformly at random then ensures (with high probability) that we include a point from this large cluster, and we can verify its robustness against the full dataset.
Finally, another technical ingredient is a de-amortization technique that converts the amortized update time of Monte Carlo algorithm (Motwani and Raghavan [999] into worst-case update time. We use it to obtain a worst-case guarantee for the diameter problem. We also note that a similar de-amortization framework (although not directly applicable our problems/setting) was recently proposed by Bernstein et al. [221]] for dynamic spanner and maximal matching problems.
1.2 Preliminaries
In this section, we introduce some notation, the problems, and necessary definitions that will be used throughout the paper.
Let P C IRd be set of points in d dimensions. Define dist,pp, ) as the distance between two points p.p' E P. Let (p, C) = minge dist(p, c) be the minimum distance between p E P and C C P. and F(c, P) maxper dist(c. p) be the furthest neighbor from a point of notation, we may use F(c, P)) to refer to arg P dist(c, (c. p) as well. Further, denote B(p,r) as the ball of radius centered at p, MEB (P) as the minimum enclosing ball of P, and conv (P) as the convex hull of P. Finally, let n be the total length of the stream given in input. We remark that n used only for the analysis, our algorithms will not need know n.
P. With slight abuse
We are now ready to state the exact definition of the problems being studied.
Definition 1.3 (Diameter Problem). Given a set of points P, the goal of the algorithm is to return an estimate diameter that is as close as possible diam (P) mmaxpp' dist(p,p')
Definition 1.4 (k-Center Problem). Given a set of points P, the goal of the algorithm is to choose a set of k points C' Ç P such that maXpe P dist(p, C.) is minimized.
The 1-center problem corresponds to the problem of minimum enclosing ball. For simplicity, we state the fully-dynamic version of the k-center problem below. The diameter problem is analogous with OPT(P) (P) being the diameter of P instead.
Definition 1.5 (Dynamic A-Apprxximaee k-Center against Adaptive Adversary). Given set of points P and a sequence of updates (insertions and deletions), the goal of the algorithm is to return at any point in time an answer d such that d E (OPT(P), a OPT(P)), for a constant a 2 1, with (P)(P) being the radius of an optimal solution to the k-center problem.
The failure probability of the algorithm, i.e., the probubility that at any point in time the algorithm returns wrong answer, should be at most 5, for arbitrary 8 E (0, 1). Moreover, the approximation factor and the update time should hold with a sequence of updates that are chosen by an adaptive adversary who sees the random bits used by the algorithm.
5

---

2 Robust representative of a point set
As mentioned in the introduction, if we do not need adaptiveness, then we can obtain a approximation for the diameter by maintaining the maximum distance from fixed point in the dataset. The key intuition here that each point in the dataset is (approximately) representative entire set for the purposes of calculating the diameter. Our first ingredient to develop our algorithms characterization of the property for point F of being representative of the set P. even
the
$ P.
Definition 2.1 (Representative Point). A point x E Rdd is representative of a point set P if m dist(a; y) I diam(P).
Figure 1: Representativeness and robustness in point set of size 12. The red point, c', is representative but not robust. The blue point, c, not part of the dataset, is both representative and e-robust for one can verify that any subset of 9 or more points from the original dataset will still contain e in its convex hull. This because e has Tukey depth 4, i.c., every halfspace passing through contains least 4 points. The shaded region indicates one such halfspace. (See Section 2. for corresponding definitions.)
1/4. In fact,
By definition, if we can maintain the maximum distance from a representative point, we always have an approximation for the diameter. In the dynamic setting however, the underlying set P is going through updates and as such, any fixed point may not remain representative after some updates. Indeed, while any P satisfies the property of being representative, if the adversary removes we will need to choose a new point. To deal with this issue, we characterize the robustness representative point with respect the point set.
Definition 2.2 (e-Robust Representative Point). A point x E Rd is an e-robustly representative of P x is representative point of all P' that satisfies PP nP (1 - for an e (0, 1).
In the above definition, the same point x should be representative of every set P' that include at least (1 fractiono of points in P. Hence, P' might also include arbitrary number of points that not in P. We refer to Fig. I for an illustration of these concepts.
The following lemma demonstrates the importance of e-robust representative point. It essen- tially states that maintaining the maximum distance from a robust representative point gives a a-approximation of the diameter, even when the original set undergoes any number of insertions and up to L<|P[] deletions.
Lemma 2.3. Assume that x E TRd is an e-robustly representative of P. For any set P' with [P' 0 Pl P)) we have diam(P))/25 maxyer P dist(r, y) diam(P').
2.1 Robust reprentatives and centerpoints
While the definition robust representatives fairly natural given our problem, it not clear whether such points exists and, importantly, whether they can be found efficiently. In this section, we show construction robustly representative points using so-called centerpoints, points sufficiently "deep" in the data. To formalize this, we need to introduce the notion of Tukey depth.
Definition 2.4 (Tukey Depth (Tukey 1975 ). Given set of n points P E Raxd, the Tukey's depth of point is the smallest number of points in any closed halfspuce that contains
is a known fact that every set of points (with no duplicates) always has a point, which need not be of the data points, of Tukey depth at least n (d + 1), and this may be tight. Such point be thought of as a higher-dimensional median of the point set; in d = 1 the median has fact Tukey useful relate the Tukey depth of a point with the size of the point set, as
depth at least n/2. captured by the following definition.
Definition 2.5 (o-centerpoint). An a-centerpoint e of point set of size n is a point that has Tukey depth at least [an], for any E [1 (

---

To gain familiarity with the definition, the mne-dimensional median is 1 //necenterp, In higher dimensions, an a-centerpoint point essentially divides set of points in two subsets such that the smaller part has at least an fraction of the points.
There several known algorithms compute a centerpoint with runtime depending the quality of the centerpoint and the number of dimensions. Ideally. we would like to find a (4/a-i)-centerpoing but this requires O( + n log n.) time by Chan (2004b), which claimed to be probably optimal. The work of Clarkson al. [1993] shows that approximate 1 (poly(d) -deettterpnn can be computed in poly(d) time with high probability. Their algorithm is based on iteratively replacing sets of d + points with their Radon point, which is any point that lies in the intersection of the convex hulls of these sets and is due to |Rdon [921]. The fastest known algorithm is due to [Har-Peled and Jones 2020] and has the following randomized guarantee.
Theorem 2.6 (Theorem 3.9 of [Har-Peled and Jones 2020]). Given arbitrary set P of points in R2, there is a randomized Monte Carlo algorithm that computes a 35 -g--eentrpoiit of in Odd log" dogg ) time with probability at least 1 p.
We next show that an a-centerpoint satisfies two key requirements: (i) is representative, i.e., it leads to a 2 upproximation of the diameter, and (ii) it is robust, ... it continues to provide a 2-approximation even after Ma (P) deletions. We begin by proving the following lemma which shows that any point in the convex hull is representative.
Lemma 2.7. Let e be a point in the convex hull P. Then, F(c, diami (P) diam(P))
Let r(-) denote the radius of a set. We immediately obtain the following corollary.
Corollary 2.8. Let e be point in the corvex hull P. Then, F(c, P) E [r(MEB(P)), 2r (r
Lemma 2.9, Any point e with Tukey depth at least 1 with respect to a set lies in its convex hull.
Combining Lemma 2.7 and Lemma 2.9 proves that any point with Tukey depth 1 is representative. Next, we show that the Tukey depth of a centerpoint for can be lower bounded, even if P goes through e| PI adversarial updates.
Lemma 2.10. Let P be a set of points and be an a-centerpoint of P. For any set P', the point c has Tukey depth at least [an t] with respect P' where t |P\ P'
In the special case where P n Pl (1 PP is satisfied, for < o,, the point e has Tukey depth at least with respect to P..
Combining Lemma 2.7 Lemma 2.9 and Lemma 2.10 we obtain the following. Corollary 2.11. Any a-centerpoint of P is e-robustly representative for any e a.
3 Dynamic algorithm for the diameter problem
We now ready to explain how to compute and maintain 2 2-approximation to the diameter of dynamic point set P, against an adaptive adversary. Let 1/4d² be a parameter, be an upper bound on the desired failure probability, and / denote the current timestep, i.e., the number of updates occurred so far.
If the size of the current point set is small, say most d we can obtain 2-approximation without centerpoint. The algorithm picks an arbitrary point in P and computes its furthest neighbor in (d5)
When the size of P is larger than d4, we compute an a-centerpoint that will be kept representa- tive point until roughly al P| deletions occur. Once we have a centerpoint c, we maintain F(c, P) using a balanced BST (e.g.. implemented as an AVL tree) that contains the distances of all points from the centerpoint. We then use a counter to keep track of the number of deletions that P has undergone since the computation of so that another centerpoint will be computed as soon stops being representative. We give a more detailed pseudocode below: queries are handled by Algorithm insertions by Algorithm 2, and deletions by Algorithm 3
7

---

Algorithm APPROXU E,,,,,
1: if P.counter 0 then
The previously computed centerpoint is still representative
2: return F(P.centerpoint, P)
3: if [P] S. d² then
Use an arbitrary point
4: Pick an arbitrary point p E
5: return F(p, P)
6: P.counter <- P|
Compute centerpoint
of P via Theorem 2.6 with ip 6/262 8: P.distances build balanced BST on Upep dist(c.
7: P.centerpoint + Find
9: return F(P..enterpointt P)
Algorithm 2 APPOXXMATEDDANEETRINRRROOY
insert p into
2: if P.counter > 0 then
3: insert dist. P.neterrppi p) into P.distances
Algorithm 3 APPOOSIATTDDAMMTTEDEEETTOOCC
1: delete p from
2: if P.counter >> then
3: delete dist (PPcenterpooint p) from P.distances
4: P.counter +- P.counter-1
We establish the approximation guarantee achieved by our algorithm in the next lemma.
Lemma 3.1. Given sequence S of n updates by adaptive adversary, with each update being either an insertion or a deletion of point, let P: be the set obtained after the first updates. The algorithm
(Algorithm 7) returns 2-approximate diameter of Po at any point in time [n], with probability at least 1 1
Next, we prove amortized bound on the cost of each operation performed by our algorithm.
Lemma 3.2. Given a sequence S of n possibly adversarial updates, let Pe be the set obtained after applying the first updates. The amortized update time per operation O(d log d (n/8)).
We are now ready to prove worst-case bound on the update time. By the discussion above, it is enough to guarantee that at times a centerpoint is available, so that we do not need to compute one from scratch before answering a query. We explain how to maintain valid centerpoint at all times when IP|| = ((d log 1.5 dlogg 1.5
s --1). If the latter assumption is not respected, we can answer each query on the fly in Odd log 1.5 d log 1.5 ") To build some intuition, consider a centerpoint e computed at time I. Point e will valid
the next e updates. Rather than waiting e|P.] timesteps, we initiate the computation of the next centerpoint e' at time 3/3/4 Pt). The computation of é' is being spread over the next 1/4- el e iterations which is still valid. This process can be implemented as shown in Algorithm where each iteration of the for loop corresponds to update.

---

Algorithm 4 DEC.ANOOTTEDOGTTTTRROOCOOOOOOTTD 9)
centerpoint +- 0
2: expiration_tims 4- 0 update_time time
D When the current centerpoint stops being representative
When to start computing the next centerpoint
4: next_centerpoint <- 0
5: next_expiration_ time f-
6: for t = l..... do
7: if' t equals expiration time then centerpoint <- next _ext__eeteppont expiration_ting time- +- seext_exprrationn time
The next centerpoint takes over
8:
9:
10:
if t equals update time then
The computation of the next centerpoint starts
11:
do in the background within 7 timesteps (cf. Lemma 3.3)
12:
Create copy of P: (filter newer points)
13:
next next_centerpoint (1/3d")-centerpoins >-centerpoint of P. with & 6/2/² Compute all distances from next centerpont (include newer points)
14:
15:
next_ _ext__xprattion___ time + Pt
16:
update_ting +- + 3/4 El P.
Lemma 3.3. The worst-case update time of Algorithh combined with the centerpoint computation of Algorithm is (dd log (n/8). This update time holds deterministically, regardless of the adversarial nature of the updates.
Finally, Theorem 1.1 follows from combining Lemma 3.1
with Lemma 3.3
Dynamic algorithm for k-center clustering
In this section, we describe our dynamic algorithm for the k-center problem. Our approach is to identify measure of robustness the number of points within a certain radius from each candidate center. Since this would be computationally expensive to calculate exactly, we use random sampling to either find candidate centers estimate the density of each candidate. We will prove that the point with the highest density provides robust center. We then cluster all points close to such a center (breaking ties assigning always the lexicographically smaller). The dynamic maintenance of each cluster will follow from the robustness of the chosen center, defined as follows.
Definition 4.1 ((e, rrobustt center). Given a point set C nxd a point x E TRd is an (f, -)rbuut center of P P n (xx 2(1 + s)'1 2 for & E [L]. 3 E [n]] and some error parameter e > O.
Our approach will reduce the dynamic k-center problem maintaining ordered sequence of at most instances II....,II, where: (1) each instance is associated with a robust-center, (2) instance I4 is constructed recursively after completing instances ..,... I 1, and (3) if. at any point during the dynamic process, an instance Z, must be reconstructed, then all subsequent instances I,.... Ix rebuilt well. We first introduce static algorithm and then discuss its robust dynamization. The pseudocode of all our algorithms is included in the appendix.
Static k-center algorithm Let p geP dist(p.q] denote the spread ratio of the point set P. C. Rd. We consider guesses & E [L]. where L [log(1+e) pl. for the optimal radius OPT(P), and run the following procedure in parallel for each guess.
dist(p.g)
For each guess (1 e) we uniformly sample actual size of the S may be optimized based on the number of unclustered points. For each sample point s E St. we compute how many other sample points lie within distance 2(1 + f- i.c., Bs, 211 + e)++1) S*). The sample point s with the highest count is chosen as a center. If is good guess (i.e., close OPT(P)), then there least one optimal large cluster that contains at least n/k points, which will provide (e, ((m/k))) robusst center.
S of OOk log L log(n/6) points from P: the
Once the sample point sf with the largest neighhorhood is selected, we gather points in within B(s 4(1 + e)+1). where the radius is doubled ensure complete coverage. We then define the

---

corresponding cluster E with cj := s" as Pn ((c,, + +) and remove its points from P before recursing. P becomes empty within & iterations, we have a good guess; otherwise, the guess is marked as low-value. We always return the smallest good guess. See the appendix for the
pseudocode.
Robust dynamization We now adapt the static algorithm to the dynamic setting. We maintain I, parallel copies of the dataset one per guess-denoted p For each cluster e we maintain two counters: nf tracks the cluster size, and m. counts how many updates can be performed before rebuilding the cluster. When m hits zero, we rebuild & and all subsequent clusters for guess
On insertion of a point p. we add to each Pt. If p falls within a current cluster C,, we add to such cluster and increment m if p is close its center. If p not covered by any existing cluster, we add it to the remainder set Q", These remainder sets allow us detect increases in OPT(P) over time. In such cases, we extract the solution from a clustering associated with a higher guess.
Deletions are handled similarly. When point p is deleted, we remove it from each P and determine whether it belonged to cluster e, If it has distance at most 2(1 + =)f+1 from cf. we decrement m and rebuild needed. If p was part of the remainder set Q', we remove it from Q' and check whether to resume a previously suspended clustering for guess f. This is because the deletion may reduce OPT(P), making previously invalid guess (1 + +)f now feasible. so, we resume clustering from the iteration it was halted.
Handling small guesses A subtle but important issue arises when the guess (1 +) is significantly smaller than OP((P). In such cases, all sample neighborhoods (s. 2(1 (1++))++1 may contain fewer than O0=-2I11 log rı) sample points, making them too sparse to be useful. To address this, whenever we observe that all sample neighborhoods in St are too sparse, we suspend the clustering process. We resume it only when a sample point in S gains enough neighbors (at least O(E -e--2oo lo), indicating that the guess may now be viable.
Let C* = .c....., off be the set of optimal centers and let e- = ........ ..) } be the set of optimal clusters. The approximation achieved by our algorithm is established via the following invariants.
Definition 4.2. At all times, algorithm satisfies the following two invariants:
disjointedness: For any i [k- 11. the set B(c, 4(1 -())4)10)))PP))) = 00, -,5ンi >
closeness: for every i k. it holds that dist C₁) < 2(1 2))+)))PT(P), that is, there exists point p from E that is "close" to center.
The bound on the update time follows the same line of reasoning as that developed for the diameter. We refer to the appendix for the details of our algorithm for k-center.
References
I. Abraham, D. Durfee, I. Koutis, S. Krinninger, and R. Peng. On fully dynamic graph sparsifiers. In I. Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyall Regency, New Brunswick, New Jersey, USA, pages 335-344. IBEE Computer Society, 2016. doi: 10. F011099FOCS200066 2016.44
https:::::/ :/to::://di... org/ 10. 1109/FOCS
K. Agarwal and R. Sharathkumar, Streaming algorithms for extent problems in high dimensions. Algorithmica, 72(1):83-98, 2015.
P. K. Agarwal and H. Yu. A space-optimal data-stream algorithm for coresets in the plane. In Proceedings of the twenty-third annual symposiun on Computational geometry, pages 1-10, 2007.
K. Agarwal, Har-Peled, and K. R. Varadarajan. Approximating extent measures of points. Journal of the ACM (JACM), 514)6606- 2004.
C. C. Aggarwal. Outlier Analysis. Springer, 2nd edition, 2016.
10

---

M. Ajtai, V. Braverman, T. Jayram, S. Silwal, A. Sun, D. P. Woodruff, and S. Zhou. The white- box adversarial data stream model. In Proceedings of the 41st ACM Symposium on Principles of Database Systems, pages 27, 2022.
A. Alokhina and J. van den Brand. Fully dynamic shortest path reporting against an adaptive adversary. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3027-3039. SIAM, 2024.
A. Athalye, L. Engstrom, A. Ilyas, and K. Kwok. Synthesizing robust adversarial examples. In International conference on machine learning, pages 284-293. PMLR, 2018.
M. Badoiu and K. L.. Clarkson. Smaller core-sets for balls. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Jamuary 12-14, 2003, Baltimore, Maryland, USA, pages 801-802. ACM/SIAM, 2003. URL http://dp. acm. org/ cwtatiii.. :f4 644240
M. Bădoiu and K. L. Clarkson. Optimal core-sets for balls. Computational Geometry, 40(1):14-22, 2008.
S. Baswana, M. Gupta, and S. Sen. Fully dynamic maximal matching in o'log n) update time (corrected version). SIAM J. Comput. 477))617-650, 2018. doi: 10.1137/1611106155 URL https::/ddi... org/10. 10. 1137/16M1106155
M. Bateni, H. Esfandiari, M. Fischer, and V. Mirrokni. Extreme k-center clustering. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5):9411-3949, May 2021. doi: 1609/aia.... $3515.16513 URL htt.hhttss///o //ojs. aaai. org/index..i.eoooooooooooggeeeee index.idexx/// www.ddx.pppp/eee hatp/AAAT/articee. wttp:i/leleeeeeeeeeeeee/e
M. Bateni, H. Esfandiari, H. Fichtenberger, M. Henzinger, R. Jayaram, V. Mirrokni, and A. Wiese. Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. In Proceedings of the 2023 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 2677-2727. SIAM, 2023.
A. Beimel, H. Kaplan, Y. Mansour, K. Nissim, T. Saranurak, and U. Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1671-1684, 2022.
O. Ben-Eliezer and E. Yogev. The adversarial robustness of sampling. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGA symposium on principles of database systems, pages 49-62, 2020.
O. Ben-Eliezer, R. Jayaram, D. Woodruff, and F. Yogev. framework for adversarially robust. streaming algorithms. ACM Journal of the ACM (JACM), 69(2):1-33, 2022.
M. Bern and D. Eppstein. Approximation algorithms for geometric problems. Approximation algorithms for Nh-hard problems, pages 296-345, 1997.
A. Bernstein and S. Chechik. Deterministic decremental single source shortest paths: beyond the (mn) bound. In Proceedings of the forty-eighth annual ACM symposium Theory of Computing, pages 389-397, 2016.
A. Bernstein, J. v. d. Brand, M. P. Gutenberg, D. Nanongkai, T. Saranurak, A. Sidford, and H. Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint arXiv:2004.084. 08432, 2020.
A. Bernstein, S. Forster, and M. Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms (TALG), 17(4):1-51, 2021.
S. Bhattacharya, M. Costa, N. Garg, Lattanzi, and N. Parotsidis. Fully dynamic k-clustering with fast update time and small recourse. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, II, USA, October 27-30, 2024, pages 216 IEEE, 2024a. doi: (0.1099FFC361226.2244.0000
htR.sttps:// /oi. 1ttg////.000//00065555566
S. Bhattacharya, M. Costa, Lattanzi, and N. Parotsidis. Fully dynamic k-center clustering made simple. arXiv preprint arXiv:2410.11470, 2024b.

---

L. Biabani, A. Hennes, D. La Gordt Dillie, M. Monemizadeh, and M. Schmidt. Improved guarantees for fully dynamic k-center clustering with outliers in general metric spaces. In Globerson, I. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang. editors, Advances in Neural Information Processing Systems, volume 37, pages 89278 39278-89306. Curran Associates, Inc., 2024. URL bttts::////// #2225ftt992teefffd0111111aaaaaaa orr.ap000....aaaaaooo-ooro---rrr
neurips cc/ Sopper-Confeencce pdf
wwwpppppppppppppcpepppepe paper_______p fiw.filllppplll htt.eee//ppprr22///12//ee
B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šmdić, P. Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning at test time. In Machine learning and knowledge discovery in databases: European conference, ECML pKDD 2013, prague, czech Republic, September 23-27, 2013, proceedings, part III 13, pages 387-402. Springer, 2013.
I. Bogunovic, S. Mitrović, J. Scarlett, and V. Cevher. Robust submodular maximization: A non- uniform partitioning approach. In International Conference on Machine Learning, pages 508-516. PMLR, 2017.
A. Borodin, R. Ostrovsky, and Y. Rabani. Subquadratic approximation algorithms for clustering problems high dimensional spaces. Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 435-444, 1999.
M. Ceccarello, A. Pietracaprina, and G. Pucci. Solving k-center clustering (with outliers) in mapreduce and streaming, almost as accurately as sequentially, Proc. VLDB Endow. 12(7): 766-778, Mar. 2019. ISSN 2150-8097. doi: 101447783317315.3173199 URL https
//doi.org/11 10. 01177///311311.3331333
T. H. Chan, A. Guerqin, and M. Sozio. Fully dynamic k-center clustering. In Proceedings of the 2018 World Wide Web Conference, pages 579-587, 2018.
T.-H. Chan, Lattanzi, M. Sozio, B. Wang. Fully dynamic k-center clustering with outliers. Algorithmica, 86(1):171-193, 2024.
T. M. Chan. Faster core-set constructions and data stream algorithms in fixed dimensions. In Proceedings of the twentieth annual symposium on Computational geometry, pages 152-159, 2004a.
M. Chan. An optimal randomized algorithm for maximum tukey depth. In SODA, volume 4, pages 430-436, 2004b.
T. M. Chan. A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. ACM, 57(3), Mar. 2010. ISSN 0004-5411. doi: 10.1145/7065991.7766666 URL https //doi.org/1n org/10....0000
T. M. Chan and Q He. More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time. In K. Buchin and E. Colin de Verdière, editors, 37th International Symposium Computational Geometry (SoCG 202/), volume 189 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1-22::14 Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz- Zentrum für Informatik. ISBN 978 978-3-95977-184-99 https:://rrpps
doi: 2tt3////.Pes.SSCCCC 220.E...222... .255. URL htgp:/unn..dd//etttttteeee/eeee
4230/LIPIcs SoCG. 2021. 25
T. M. Chan and V. Pathak. Streaming and dynamic algorithms for minimum enclosing balls in high dimensions. Computational Geometry, 47(2):240-244 2014.
M. Charikar, C. Chekuri, T. Feder, and R. Motwani. Incremental clustering and dynamic information retrieval. In Proceedings of the twenty- annual ACM symposium on Theory of computing. pages 626-635, 1997.
Y. Cherapanamjeri and J. Nelson. On adaptive distance estimation. Advances in Neural Information Processing Systems, 13:11178-11199 2020.
Y. Cherapanamjeri, Silwal, D. P. Woodruff, Zhang, Q. Zhang, and S. Zhou. Robust algorithms on adaptive inputs from bounded adversaries. In The Eleventh International Conference on Learning Representutions, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.nes 2023. URL. https://openrrvviert net http:///e/.orrr.....///.OOOO
12

---

J. Chuzhoy and S. Khanna. A new algorithm for decremental single-souree shortest paths with applications to vertex-capacitated flow and cut problems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 389-400, 2019.
J. Chuzhoy and R. Zhang. A new deterministic algorithm for fully dynamic all-pairs shortest paths. In Pruceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1159-1172, 2023.
K. L. Clarkson. Coresets, sparse greedy approximation, and the frank-wolft algorithm. ACM Trans. Algorithms, 6(4):63:1-63:3 63:30, 2010. doi: 10.1 (0.1145/182477711884788 URL hotthttts://dd org/ 10. 1..114//182477/ 1824783
K. L.. Clarkson, D. Eppstein, G. L. Miller, C. Sturtivant, and S.-H. Teng. Approximating center points with iterated radon points. In Proceedings of the ninth annual symposium on Computational geometry, pages 91-98, 1993.
K. L. Clarkson, E. Hazan, and D. Woodruff. Sublinear optimization for machine learning. ACM. 59(5):23:1223:99, 2012. doi: 241144//7776536237166655 URL https://doi..o.. or0/ 2371656. 2371658
E. Cohen, X. Lyu, J. Nelson, T. Sarlós, M. Shechner, and U. Stemmer. On the robustness of countsketch to adaptive inputs. In International conference on machine learning, pages 41 4112-4140. PMLR, 2022.
V. Cohen-Addad, C. Schwiegelshohn, and C. Sohler. Diameter and k-center sliding windows. In 43rd International Colloquium Automala, Languages, and Programming (ICALP 2016), pages 19-1. Schloss Bagstuhl-Leibrngg Leib--i--zzetrurrn Zentrum für Informatik, 2016.
S. Coy, A. Czumaj, and G. Mishra. On parallel k-center clustering. In Proceedings of the 35th ACM Symposium Parallelism in Algorithums and Architectures, SPAA '23, page 65-75, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9781450395458, doi: 10.1 14.1/45//58888111 1.191115551555 httpss/tt:://att
10. 1ee.11115335555 3591075
A. Czumaj, G. Gao, M. Ghaffari, and S. H.-C. Jiang. Fully scalable mpc algorithms for euclidean k-center. arXiv preprint arXiv:2504. 16382, 2025.
M. De Berg, L. Biabani, and M. Monemizadeh. k-center clustering with outliers in the mpe and streaming model. In 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 853-866 IEEE, 2023.
Ö. Egecioglu and B. Kalantari. Approximating the diameter of a set of points in the euclidean space. Information Processing Letters, 32(4):205-211, 1989.
Evald, V. Fredslund-Hanser M. Probst Gutenberg, and C. Wulff-Nielsen. Decremental apsp in unweighted digraphs versus an adaptive adversary. In 48th International Colloquium Automata, Languages, and Programming (ICALP 2021), volume 198, page 64. Schloss Dagstuhl-Leti Leibnniz- Zentrum für Informatik, 2021.
T. Feder and D. Greene. Optimal algorithms for approximate clustering, In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 434 444, 1988.
Y. Feng and D. Woodruff. Improved algorithms for white-box adversarial streams. In International Conference on Machine Learning, pages 9962-9975. PMLR, 2023.
Y. Feng, A. Jain, and D. P. Woodruff. Fast white-box adversarial streaming without random oracle. In Proceedings of the 41st International Conference on Machine Learning, ICML'24. JMLR.org. 2024.
D. V. Finocchiaro and M. Pellegrini. On computing the diameter of a point set in high dimensional euclidean space. Theoretical Computer Science, 287(2):501-514 2002.
S. Forster and A. Skarlatos. Dynamic consistent k-center clustering with optimal recourse. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 212-254. SIAM, 2025.
13

---

E. Frandi, M. G. Gasparo, S. Lodi, R. Nanculef, and C. Sartori. A new algorithm for training svms using approximate minimal enclosing balls. In I. Bloch and M. Cesar, editors, Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications 15th Iberoumerican Congress on Pattern Recognition, CIARP 2010, Sao Paulo, Brazil, November 1,, 2010. Proceedings, volume 6419 of Lecture Notes in Computer Science, pages 87-95. Springer, 2010. doi: 10. 978-3-642- 16687-76660 176---76667666666 URL http:////oo..or////../
10. 1007/9707/7888 642- 16687-7_16
A. Goel, P. Indyk, and K. R. Varadarajan. Reductions among high dimensional proximity problems. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 769-778, 2001.
T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical computer science, 38:293-306, 1985.
G. Goranci, M. Henzinger, D. Leniowski, C. Schulz, and A. Svozil. Fully dynamic k-center clustering in low dimensional metrics. 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), pages 143-153. SIAM, 2021.
M. P. Gutenberg and C. Wulff-Nilsen. Decremental sssp in weighted digraphs: Faster and against an adaptive adversary. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithmss, pages 2542-2561. SIAM, 2020.
S. Har-Peled and M. Jones. Journey to the center of the point set. ACM Transactions on Algorithms (TALG), 17(1):1-21, 2020.
Har-Peled, P. Indyk, and R. Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory Comput.. 8(1):321-350) 2012. doi: (0-4066/TOC.2012.0004400 URL httpp://doii org/ 10. 4086/toc. 2012. v008a014
A. Hassidim, H. Kaplan, Y. Mansour, Y. Matias, and U. Stemmer. Adversarially robust streaming algorithms via differential privacy. J. ACM, 69(6), Nov. 2022. ISSN 0004-5411. doi: 10.1 145/ 3556972. URL httph::////ee //doi. org/10. 1145/3556972
D. S. Hochbaum and D. B. Shmoys. A unified approach approximation algorithms for bottleneck problems. Journal of the ACM (JACM), 3333)5333550 1986.
W.-L. Hsu and G. L. Nemhauser. Easy and hard bottleneck location problems. Discrete Applied Mathematics, 1(3):209-215 1979.
A. Ilyas, L. Engstrom, and A. Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. In International Conference on Learning Representations, 2019.
Indyk. Dimensionality reduction techniques for proximity problems. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms,, pages 371-378, 2000.
P. Indyk. Better algorithms for high-dimensional proximity problems via asymmetric embeddings. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 539-545, 2003.
Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse of dimension- ality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (STOC), pages 604-613. ACM, 1998. doi: 10. 10.1145/276698.276777
H. Kaplan, Y. Mansour, K. Nissim, and U. Stemmer. Separating adaptive streaming from oblivious streaming using the bounded storage model. In Anmual International Cryptology Conference. pages 921 Springer, 2021.
A. Karczmarz, A. Mukherjee, and P. Sankowski. Subquadratic dynamic path reporting in directed graphs against an adaptive adversary. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pages 1643-1656, 2022.
Kumar, J. S. Mitchell, and E. Yildirim. Approximate minimum enclosing balls in high dimensions using core-sets. Journal of Experimental Algorithmics (JEA), 8:1-1, 2003.
14

---

A. Kurakin, J. J. Goodfellow, and S. Bengio. Adversarial machine learning at scale. In International Conference on Learning Representations, 2017.
J. Lacki, B. Haeupler, C. Grunau, R. Jayaram, and V. Rozhoñ. Fully dynamic consistent k-center clustering. In Proceedings of the 2024 Anmual ACM- SIAM Symposium on Discrete Algorithms (SODA), pages 3484. SIAM, 2024.
W. Liu, Wang. S. Kumar, and S.-F. Chang. Hashing with graphs. In Proceedings of the 28th International Conference on Machine Learning (ICML), 2012.
Y. Liu, X. Chen, C. Liu, and D. Song. Delving into transferable adversarial examples and black-box attacks. In International Conference on Learning Representations, 2017.
A. Madry, A. Makelov, Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
G. Malkomes, M. J. Kusner, W. Chen, K. Q. Weinberger, and B. Moseley. Fast distributed k-center clustering with outliers on massive data. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran As- sociates, Inc., 2015. URL Utt./tttss///pproceeddagg
neurips...... cc/ saccppppr___ ff files/ www.eeeeeeeeeeeeeeeeeeaaaeeeeeee pappp /015// papperrpdfff
I. Mironov, M. Naor, and G. Segev. Sketching in adversarial environments. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 651-660) -600, 2008.
R. Motwani and P. Raghavan. Randomized algorithms. In M. J. Atallah, editor, Algorithms and Theory of Computation Handbook, Chapman Hall/CRC Applied Algorithms and Data Structures series. CRC Press, 1999. doi: 10. 01000/997814244500---4 URL https:://poo org/rr..r/0 1201/
9781420049503-c15
D. Nanongkai and T. Saranurak. Dynamic spanning forest with worst-case update time: adaptive, las vegas, and (n1/2-e)-time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1122-1129, 2017.
D. Nanongkai, T. Saranurak, and Wulff-Nilsen. Dynamic minimum spanning forest with sub- polynomial worst-case update time. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 950-961. IEEE, 2017.
K. Onak and R. Rubinfeld. Maintaining large matching and small vertex cover. In L. J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 457-464. ACM, 2010. doi: 10.1145/1806689, 806889066669777.7 1806753. URL https:///dt: org/10. 1145 1104681886689... 1806753
R. Pagh, F. Silvestri, J. Sivertsen, and M. Skala. Approximate furthest neighbor in high dimensions. In Proceedings of the 31 International Conference on Data Engineering (ICDE), 2015.
P. Pellizzoni, A. Pietracaprina, and G. Pucci. Adaptive k-center and diameter estimation in sliding windows. International Journal of Data Science and Analyties, 14(2):155-177 2022.
M. Probst Gutenberg, V. Vassilevska Williams. and N. Wein. New algorithms and hardness for incremental single-source shortest paths in directed graphs. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pages 153-166, 2020.
J. Radon. Mengen konvexer körper, die einen gemeinsamen punkt enthalten. Mathematische Annalen, 83(1):1 13--115, 1921.
M. Roghani, A. Saberi, and D. Waje. Beating the Folkiore Algorithm for Dynamic Matching. In M. Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 Leibniz International Proceedings in Informatics (LIPIcs), pages 1 111:1-111:23, Dagstuhl, Germany, 2022. Schloss Dagstuhl- Leibniz-Zentrum für Informatik. ISBN 978-3-95977- 217-4. doi: wtw. document / 10. 4230/LIPICS /tI//IIIIISSSS ITCS 2022.
URI, htt.llhtts://// htttps:///rops.......t http//drpp...ssuuullll dagstuhl det.edieeeetteeeeeeeeeeeee
15

---

M. Schmidt and C. Sohler. Fully dynamic hierarchical diameter k-clustering and k-center. arXiv preprint 1908 1011:1998.00645,, 2019.
M. Stoeckl. Streaming algorithms for the missing item finding problem. In Proceedings of the 2023 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 793-818. SIAM, 2023.
D. M. J. Tax and R. P. W. Duin. Support vector data description. Mach. Learn., 5:(1):45 66,, 2004. doi:
BTA.:///AAA..0000008........ MACH. 0000000088 60811 49
URL htttps:///oi.org: org/10gg//.. 1023/B
C. Tosh and S. Dasgupta. Diameter-based active learning. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
F. Tramèr, D. Boneh, A. Kurakin, I. Goodfellow, N. Papernot, and P. McDaniel. Ensemble adversarial training: Attacks and defenses. In 6th International Conference on Learning Representations, ICLR 2018-Conference Track Proceedings, 2018.
J. W. Tukey. Mathematics and the picturing of data. In Proceedings of the international congress of mathematicians, volume 2. pages 231.33.. Vancouver, 1975.
D. Waje. Rounding dynamic matchings against an adaptive adversary. Proceedings of the 52nd Annual ACM SIGACT Symposium Theory Computing, pages 194-207, 2020.
D. P. Woodruff and Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1183 1 196. IEEE, 2022.
H. Zarrabi-Zadeh. almost space-optimal streaming algorithm for coresets in fixed dimensions. Algorithmica, 60:46-59, 2011.
H. Marrabi-Zaded and T. M. Chan. A simple streaming algorithm for minimum enclosing balls. In Proceedings of the eighteenth anmual Canadian Conference on Computational Geometry, pages 139-142, 2006.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction clearly and accurately state the claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The assumptions made in the paper as well as the results are clearly stated and therefore the limitations are clear.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

Justification:
A complete proof of theoretical results is provided.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: The paper makes a significant theoretical contribution and does not include experimental results.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
18

---

Answer: [NA]
Justification: The paper makes a significant theoretical contribution and does not include experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https /mips.ccc/pullc//uuui guwde//ddee/ee/ Cot//ooooeeeiiseeeeeeee wwwpobmmsssioooooooooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper makes a significant theoretical contribution and does not include experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper makes a significant theoretical contribution and does not include experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
19

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper makes significant theoretical contribution and does not include experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Conforms the guidelines
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical in nature and does not have societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not use crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
22

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: No LLMs were used in conducting the research generating the results.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https: httt::////errrrsssc/////oeeerrre ccceooofeeeeence/222///1/1 for what should or should not be described.
23

---

A Further related work
Concerning the diameter problem in high-dimensions, a better-than-two approximation can be achieved in the oblivious adversary setting. A long line of work [Borodin al. 1999 Egecioglu and
Kalantari 1989 Finocchiaro and Pellegrini 2002 Goel et al. [001][ndyk] 2000 2003 culminated
in fully dynamic (1 + e) approximmaee algorithm with amortized update time O by Indyk 2003). A (v2 + e) appprooxiinttoon with Odd log n) amortized update time is achieved by the works of [Agarwal and Sharathkumar, 2015. Chan and Pathak 2014).
While our focus is on high-dimensional spaces, the diameter problem is well-understood for low, fixed dimensions. Indeed, it is relatively simple to obtain a (1 + c) eaapproximation by maintaining 1/c L(()(d) different directions (Agarwal et al., [2004] Agarwal and Yu 2007 Chan [2004a] Zarrabi-Zadeh 2011] The number of dimensions can often be reduced by using dimensionality reduction, however, the above approaches struggle even with log n dimensions, due to the exponential dependency on d, which renders them inapplicable in practical scenarios.
Another line of work considered the closely related problem of minimum enclosing ball (MEB).
corresponds to the 1-center problem, and a c-approximate MEB directly implies a (v2 c)-
approximate diameter, for d large enough. A number of streaming and dynamic MEB algorithm
have been developed (Fgecioglu and Kalantari 1989 Aggawal and Sharathkumar 2015 Chan and
Pathak 2014 Zarrabi-Zadeh and Chan [2006]. The best known dynamic MEB algorithm is 1.22-
approximation by Chan and Pathak [0144] that builds upon the streaming algorithm of Afgrgall and
Sharathkumar (0155). which is based on coresets [Bãdoiu and Clarkson 2008 Kumar et al. 2003
The k-center problem was first studied by Charikar et al. [197]] in the incremental setting (where the points are inserted and the goal is to maintain an approximate solution), who introduced the doubling algorithm, achieving an 8-approximation with an amortized update time of (l)). Subsequent work by Chan et al. [2188) presented randomized algorithm that maintains (2 + e-aappoxximation with O O log p) amortized time per update, with p being the aspect ratio. For low-dimensional spaces, the work of [Goranci et al. 2021] provides (2 + e aapproximate deterministic algorithm with update time (2/c)o(4H)RR))) (RP), Most recently, Bateni et al. [2033] extended these results general metric spaces, providing an optimal (2 + E) -ppproooiee randomized algorithm with amortized update time O(k -ool log(n, A)). Additionally, they developed a deterministic algorithm with approximation
factor Ominn (k; Tog: log
log(n/K2
}). Another closely related line of work on consistent k-center clustering
has focused on algorithms for h-center with small recourse Lacki et al., 2024 Bhattacharya et al..
2024a b Forster and Skarlatos) 2025
There is a large body of work on dynamic problems against an adaptive adversary. These include convex hull in two and three dimensions [Chan] 2010 geometric set cover (Chan and He 2021].
and numerous graph problems such as matching [Wajc] 2020.
Roghani et al. 2022]. spanning
forest Nanongkai and Saranurak 2017 Nanongkai et al. 2017 spanners [Bernstein al. 2020
incremental single-source shortest path [Probst Gutenberg et al. 2020 Alokhina and van den Brand
2024
decremental single source shortest path [Bernstein and Chechik 2016 Chuzhoy and Khanna
2019
Gutenberg and Wilfe-Nilsem] 20220] general single source shortest-path [Karezmarz et al.
2022
and all pairs shortest paths [Evald et al. 2021 Beimel et al. 2022 Chuzhoy and Zhang 2023
Several notions of black-bor and white-box adaptive adversaries have been studied in the streaming model [Ben-Fliezer et al., 2022 Kaplan et al.
Cohen et al. [022]. The white-box streaming 2022 Research in the white-box model has focused
2021
model was recently introduced by Ajtai et al.
on graph matching and heavy hitters (Sce e.g.. Ajtai et al. 2022 Alokhina and van den Brand 2024
Stoeckl 2023
Feng and Woodruff 2023
Feng ct al. 2024
There are also a number of other algorithms for distance and clustering related problems in various
models of computations. including dynamic [Chan et al.) 2018 Schmidtt and Sohler 2019 Goranci
et al. 2021 Chan et al.] 2024. Biabani et |004], streaming Ceccarello et al.
2019 De Berg
et al. 2023], sliding window [Cohen-Addee Addad et al. 2016] WWodruff and Zhou| 2022 Pellizzoni et al.
2022 and massively parallel computation Malkomes et al. [2015), Bateni et al. 2021 Coy et al.
[2023] J. Czumaj et al. (2025). These results however do not apply to our more stringent setting of
high dimensions against an adaptive ad adversary.
24

---

B Missing Proofs and Pseudocode
B.1 Robust representative
Lemma
2.3 Assume that x E TR is an c-robustly representative of P. For any set Pt with PP - -e]lP,, , we have tiam(P")) & maXye dist(z, y) S diam(P").
[P"
Proof. Recall F(x, P) == maxye r dist(r; y) from Section 1.2 The first inequality follows from the triangle inequality. For diametral pair y, P with dist(y, 2) diam (P)m we have
(P' = dist(y, 2) I dist(y, .² + dist(z, x) S max dist(x, v) = 2F(x, yEPr
Then, the second inequality follows from the fact that x is a robust representative point of P and [P'n > (1 P) That is, is representative point of P', so F(z, P') I diam(P') holds. D
Lemma 2.7
Let e. be a point in the convex hull of P. Then, Fc, P) (dimm(P) diim(())
Proof. If P. then the claim follows trivially. Suppose that c & P and let P be the furthest point from e such that p = F(c, P). The inequality F(c, P) 2 (iam(P)/2 follows from the triangle inequality. We now prove that Fcc, P) S tiam(P) by showing that there is a point c' such that: (i) E P and (ii) dist(c',p) 2 dist(c,p) This will finish the proof since diam () 2 dist(c', p) by definition.
Observe that the f2-distance function dist(r, p) is continuous and convex with respect to x E conv ()) for fixed point p. The convex hull is non-empty because it contains and is compact because it a closed and bounded set. Moreover, by the extreme value theorem, we know that the function dist(x, p) attains its maximum on any compact set. Observe however that dist(x, p) is convex function, which means it attains its maximum value over the convex hull on one of the vertices. Since conv (P)) this means that there exists at least one vertex e' such that dist (c', Since any vertex of conv( is in P, this proves that
.p) dist(c.
F(c, P) = pist(c,p) S dist(c' pp) S ((d,P)) S diam(P).
L
Corollary 2.8 Let e be point in the corvex hull P. Then, F(c, P) E ((MMEE(P)),2(MMBB))))
Proof. The ball B centered at c with radius F(c, P) encloses all the points. Moreover, by the above proof, ball that encloses both e' and F(c, P) must have radius at least P)/2.
Lemma 2.9 Any point e with Tukey depth least 1 with respect to a set lies in its convex hull.
Proof. Suppose that lies outside of the convex hull of P, i.e., e and conv(P) are disjoint. Since cPnv(P) is closed and compact convex set and so is {c}, we can apply the following version of the hyperplane separation theorem: If two disjoint convex sets are closed and least one of them is compact, then there is hyperplane h that strictly separates them. Then, we observe that the existence of l contradicts the fact that e has Tukey depth at least 1. This is because the halfspace defined by from c's side contains and has no point from P, which would mean that c has Tukey depth zero. O
Lemma 2.10
Let P be set of points and be an a-centerpoint of P. For any set Pt, the point has Tukey depth at least [on 1) with repsect to P' where I = =I |P\P') P').
In the special where P n P (1 PP is satisfied, for e a, the point has Tukey depth at least with respect to P'.
Proof. Since e is an a-centerpoint of P, any closed halfspace h containing c has at least [an] points from P. Then, å contains at least [an] points from Pl, since at most t points from P are not in Pl. Therefore, e has Tukey depth at least [an] t = [an t with respect to P'. For the second part of the Lemma, observe that if < then
Jan t 2 an IPPP
(n PnP
+ (1 - E)n an 0.
Since Jan t] is integer, it follows that it is at least 1.
25

---

B.2 Diameter
Lemma 3.1 Given a sequence S of n updates by an adaptive adversary, with each update being either an insertion or deletion of point, let Pt be the set obtained after the first t updates. The algorithu APPROXIMATEDIAMETERR
(Algorithm 1) returns 2-approximate diameter of Pt. at any point in time i. E [n], with probability at least 1 6.
Proof. Fix an arbitrary t E [n]. We prove that our algorithm returns a 2-approximate diameter by either computing it statically (Line 5) or by using centerpoint (Lines 2 and 9). In the first case, when the algorithm returns F(p, Pt) for some p E Pt, a 2-approximation of the current diameter immediately follows.
If a centerpoint e is available, then the algorithm returns Pt). Suppose that e was computed at time to for Pt... By Theorem 2.6] c is an (1/3d")-centerpoi)) -centerpoint of Pt., with probability at least 1 - s.. By Corollary 2.11 e also an s-robust representative of Pt, where & = 1 1/4d². We now show that e is a representative point of the current point set. To this end, we prove that P. n Peal > (1 - a) Ptol- is easy to verify that the following invariant holds
PPnn Ptll = Ptol - PP Piol 2 IPt.l - (cl P.counter) > (1 E) Ptol
since, any time that a point is deleted, P.counter is decremented by one and P.counter can only take Ptoll |}. With the above, P: satisfies Definition 2.2 and thus e is representative
on values in e EPtg point of P.. We conclude that by [eema 2.3] Fcc Pt) gives a two approximation to diam Pt).
It remains to bound the probability of failure. The only randomness used is in Theorem 2.6 and if the algorithm succeeds, the 2-approximation holds for all updates, even adaptive ones. Specifically, the success of a query at time i depends only on whether e was a 1//3ddd)=ceeeerpppp
of Pro Since Theorem 2.6luses fresh randomness independent of Ptgy the adversary cannot influence its outcome. In particular, the adversary cannot retroactively change Pt.. This means that each centerpoint computation fails with probability at most y. independently of the adversarial nature of the updates. By taking union bound over the at most centerpoint computations, we have
5 22
Pr Algorithm 1 fails) S Pr[3 "bad" centerpoint]
d.
Given a sequence S of n possibly adversarial updates, let P. be the set obtained after applying the first updates. The amortized update time per operation (d log dllog(nn (n/6)).
Lemma 3.2,
Proof. Note that insertions and deletions are handled in Odd n) time by Algorithm 2 and Al-
gorithm 3
When the adversary issues a query time t E [n]. there are three possible cases. If P.counter is not zero, then the query time is given by simple O(1)-time lookup operation (Line 2).
If P.counter is zero and PAl = Odd), then the query time is (dd = O(d).
The most interesting case is when P.counter is zero and [P|] > d², which will be proved by induction on the number of centerpoints. For the base case, the first centerpoint computation takes (d log d'log'(n (n/8) +d PPl log PP.) and can be amortized over the first Pt| 2 d' insertions. For the inductive step. we amortize the computation updates that occurred between time 4++1 and time 4, when the computation of the i-th centerpoint occurred. By induction, the computation of the i-th centerpoint is amortized over updates prior to 4, so it does not affect the amortization on subsequent updates. The total computation to amortize is Odd log" d log"(n// (n//)) d|Pt... log |P 1. Now, recall that 4,41 2 el e d² by the centerpoint property, and observe that
the (i + 1)-th centerpoint at time f++1 over the
P
Prr + 1:-1-4 S 0(18s),
4+1 1
4+1 - 14
proving the claimed amortized time.
The worst-case update time of Algorithm I combined with the centerpoint computation of Algorithm is O(d5 log ( This update time holds deterministically regardless of the adversarial nature of the updates.
Lemma 3.3
26

---

Proof. The computation of a new centerpoint c' at time t happens sequentially in three steps:
1. Create of copy of Pt in T1 timesteps, incurring (IPa) + Ti) O(d P.l) operations. To avoid conflicts, add to each point an entry specifying the time in which it was inserted and another entry for the time in which it was deleted (if any). Moreover, we also maintain the points that were deleted in subsequent timesteps l' ( + Ti] in separate array, so that creating a copy of Pt does not conflict with P/- The number of extra operations required is ( dd log n), which we account for in the total complexity of this step.
2. Compute a new centerpoint c' in T2 timesteps, incurring Odd log" (loo((n/)) operations.
3. Scan all of the points present to build an AVL tree with all distances from c' in T's timesteps, incurring (PP + Ti + T2 Ts) O(d log PPl)) operations. For this step, we use the same strategy as earlier to avoid creating any conflicts. The overhead incurred to handle extra copies of recently deleted and newly added points is at most O T2 T3d log n).
This computation starts at time and finishes at time t + T = = ++ + T3, and, at each timestep. up to C d3 log!.$ d (11g2/((10) operations can be performed, for some constant C' >> O. For our worst-case update time guarantee to hold, we need to prove: (1) the computation of c' finishes before the expiration of the current centerpoint; (2) no two centerpoint computations overlap. We prove both conditions by induction of the number of centerpoints. We assume that the computations of centerpoints consecutive, since whenever the size of the dataset drops within Odd*), we can compute the diameter on the fly. For the base case, we observe that the first centerpoint is being computed when P (dd)). by the previous reasoning. Therefore, the algorithm iterations to compute it, while resorting to the on-the-fly computation before the centerpoint is ready,
spend (dd)
For the inductive step, let la be the point in time when the current centerpoint was computed. The dlog"(n//) (n/8) + d Pa log P. + dT log [P:)). For (1), the computation
total computation is (d log d d'log of d', which starts at 3</4| tol should finish within S Pt, iterations. This is verified since
d log" d dolog (n/6) + dl P log P.l + d' log Pal
d²
log' 1.5 d (logg-((//00) (m/8)+ P E|Ptul Cd
C d log" 1.5 dlog 1.5 (n/8)
C
12
where the last inequality follows from IP.ol > lid log 1.5 dlog21((n) and [P/] + T < 3 3/
For (2), we have that the computation of the successor d' will start at time + +3/44| Ptl. which is
always greater than t s/4|Prgl because PP/ 2 (1 - P)o > PPol
B.3 k-center clustering
Algorithm 5 INIT(P, k,
Input: The input set P, the dimension d and the error parameter c.
1: for e == to L do
2:
pê < is copy of the point set
3:
Initialize two sets Cte + 0 and e 0 as the set of centers and clusters
4:
C² C²,Q'r CLUUSTERING e, 1)
5:
The remainder set Q' is maintained as too low certificate for the guess (1 + e)
6: Let E [Z.] be the smallest index for which Q' is empty
7:
Return C* and Cl
B.3.1
Proofs
B.4
Correctness Analysis
This section is devoted to proving that our algorithm computes and maintains a (1++) approximation.
We first introduce some notation. Recall that we consider L. guesses (1 +c)) (1 +c) .... e)+
for the optimal k-center radius OPT(P). Throughout, we fix the guess (1 + e)f < SPPT(P) <
(1 + +1+
27

---

Algorithm 6 CLUSTERING d,e,
Input: The input set X, the dimension d, the enror parameter the guess L.
Output: (re-) ree)ccosttuucts clusters e ,,, , while clusters e,, :. e are fixed.
1: Let Y <- X be copy of X
2: while Y not empty and I k do
3: Let S be set sampled u.a.r. from Y (cf. Lemma B.3
4:
c + arg max, [3 2(1 +) n (|Y] or [S
if [B(c 2(1 +s) n [ or |s < (1 =) (Y) then
5:
4(k-1)
6:
The guess (1 =) is small for OPT(P)
7:
Break the while-loop
8:
C B(c, 4(1 4(1+ +))+t) n,, cluster around of
9:
m < 21 2(1 + + nY, robustness of of
10:
nf (B(c), 4(1 4(1+)))+)) )NY)))))))) number of points in e
11:
Add & to C and Y Y < (B(((C) 4(1 + +
i ++11
Return C²,, Y, and the clusters e (ef,.....00 C
Algorithm CLUSTERINGI
PPPP. C², e where E [L]
Input: & copies p .t.... p insertion of p. The sets Oe and e are the set of centers and clusters for the guess E L.
p of the set of points that have been inserted but not deleted before the
1: for 8 0 to I. do
2: Insert into p
3: if there is arg min for which B(c,, 4(1 +))+1) then
4:
Insert p into cluster C
5:
p E (c, 2(1 + +) then
6:
m m
7:
else
> is not covered by the current set of clusters for the guess (1 + z) if there are j- k clusters then
8:
9:
C C²Q'" + C C Q³, e'U CLUISTERING(DD).4......
10:
else
11:
Add to the remainder set Q'
12:
Let E [L] be the smallest index for which Q' is empty
13:
Return Ctl and gl
For any point p P. let c² (p) denote the optimal center assigned to p, i.e., the center of such that p E C. Similarly, given any set of l centers C {ci..... .c...... C& Rd let c(p) C' denote the center to which is assigned in the clustering induced by C, ie., the center c, such that E C, For the guess (1 + =) the offline algorithm INIT(P, d, k, E) returns a set C = {cf", ......c... of of s centers. Our goal maintain both the disjointedness and the closeness invariant.
Note that it immediately follows from Definition 4.1 that (e*, 1)-buuust center of C respects the closeness invariant.
Lemma B.1. If both invariants hold for all clusters e for [f], we have a 4(1 + E) approxxmmat solution for the k-center clustering of the point set P.
Proof. For the approximation factor, for every f and for every point p ef", the closeness invariant guarantees that
dist(p, c:) I dist(p, (p) + dist(c"(p), of) OPT(P) + +PP((P) dist CT),
is at most 4(1 + O)PP() To show that all points are clustered, we construct set (pi..... Pk with each point at pairwise distance greater than 20PT(P). Let pa ef be the point closest to of for which it holds that dist(p,, cf) 2(1 ()PT()) For any pj with of i, it holds that
28

---

Algorithm 8 CLUSTERINGDLLLTONNP
P p, C² e where l [L]
Input: copies p1 ,.... P of the set of points that have been inserted but not deleted before the insertion of p. The sets Ce and et are the set of centers and clusters for the guess & E L.
1: for é = 0 to L do
2: Delete p from pe
3: if there exists an i E [b] for which p E e then
4:
Delete from cluster ç
5:
if E B(c, 2(1 + e)++1) then m < m -1
6:
7:
if mf equals zero then C² C²,Q', e t CLUSTERING(U) d, d,),
8:
9:
else
pp Q', i.e., is not covered by the current set of clusters for the guess (1 + z) Q' + Q
10:
> Delete p from the remainder set Q' Let L |C|| be the number of clusters stored for the guess (1 + e)e
C Q', o CLUSTERING((" d, e,++1
13: Let [7] be the smallest index for which Q3 is empty
14: Return C" and el
dist(p,, 4' =(1+))) by the disjointedness property. Therefore, dist(p:. Pj) 2 dist(p;, o dist(p;, cf" 2 4(1 (I)P)() - 2(1 + +))OP(PP) 20PT(P). This means that each p; belongs to a different optimal cluster C, Hence, all optimal clusters are covered.
Thus, prove correctness, it enough to show that our invariants hold throughout. We will need few auxiliary definitions and lemmas.
The centers Ce = =(ch" ...,,.""..""""..... oft'
are ordered according to the iteration in which they were found by Algorithm 6f that is, of is computed first, followed by cz and so on up of Observe that the centers of ,f. are obtained from sampled points af .a...," that are sampled from optimal clusters. Suppose order the optimal clusters that af is sampled from the optimal cluster ei and up af that is sampled from the optimal cluster e7. Observe that if f < k. there optimal clusters from which we have not sampled any point. In particular, place these clusters arbitrarily after the last optimal cluster eÿ for which we have the last sampled point af"
We first prove that the Algorithm INIT (Lemma B.4) satisfies both invariants and that constructs centers that are (e*, L C) rrobuustt. Consider an iteration E [f] of Alg. 6 We now prove that af", if sampled, a robust center for C.
Lemma B.2. At iteration i, let of be the point that is sampled from the optimal cluster Cj The point of is an (e*, -robuuutust center. That is, it satisfies e; c. B(a ,2(1 + +)f*+1 +1).
Proof. Since of C and the cluster C that is centered the optimal center of has radius OPT(P"), ), we conclude that dist(g, af S dist(q, ct) + dist(c;, , af)) < 20PT(PP) < 2(1 e)t'+ +1 for any point q E C₁ Thus, the claim of this lemma holds.
Let us define inactive points iteration 1, we have I = @ and AC," pe" We say that optimal cluster Cj is active at iteration if C & IN otherwise, ej is an inactive cluster. Next, we prove that if there is a center sufficiently robust, then we expect be able to identify it through our sampling process.
u and active point AC p \IN the first
Lemma B.3. Consider a timestep t E [n] and an iteration i E [f] of Algorithm CLUSTERING. Define
N = AC,", and N = |C nec With failure probability at most 8, we identify a (E*, 4(k-))) robust center successfully through our sampling process. Moreover, the total computational cost of sampling and counting is bounded by Ó(min (k - i) i)?,((k i)N.-11).
N.
29

---

Proof. We consider two possible cases based on the value of k - i. If (k - i) S N set | = C(k -) log log(n/)), for some sufficiently large constant C' > Then, using a simple Chernoff bound argument, is easy verify that with probability least 1o (p)-a our sampling process satisfies the following two conditions:
If optimal active cluster is small, i.e., N
N then |S n 4(k
|
3(k-1))
2 If an optimal active cluster is large, i.e., N 2
Ni-1 then |S n c 3(k-t)
unclustered points, the above conditions hold, then the cluster with the highest count provides a sample point that (E", Ni-1 -robust. The cost of this process is bounded by (( = Ō(( - 1)?) = Ö(VkN,11) by the assumption on k.
Ni- Since there exists an optimal cluster with at least (K-1)
1(k-()
In the other case, (A: i) 2 2/3 we use lower sampling probability and show that we can still find robust center. Let us set | = CV log I. log(n/)). We compute exactly for each q E Sf the value of [B 2(1 + +1) ny and select the point with the highest count. To show that we find a robust center, we proceed with case distinction. If there are at least vík - i) clusters of size at least N,, /4(k i). through a similar Chernoff bound argument, we are ensured that there is a sample point from one such clusters which provides the desired robust center. Otherwise, the smallest (k- - i) / (l: a) clusters contain at most N points out of N1-1. This means that the largest cluster has least N,- /2 (k- i) points, and, through analogous Chernoff bound argument, we can prove that one such point will be clustered. The cost of this process is bounded by Ó(1S)) (( = Ólvik - i) = Ō((k ))
By union bound over the at most k clusters and iterations per guess f E [L], the probability that 6_
none of them fail, is at least (o)) 2 1- 2n since k S n. Further, by a final union bound on the number of timesteps E [n]]. the probability of failure is at most 6. Finally, we remark that the algorithm does not need to know n in advance; the same guarantee can be obtained by replacing n with f, as in the diameter case. We also note that the failure of this randomized process cannot be affected by an adversary.
Lemma B.4. After we invoke Algorithm (N, k, each center of is (0,,IACH,,l1 i))- robust and both of our invariants hold.
Proof. Let us consider the iterations of Algorithm CLUSTERING for the guess (1 + E) such that (1 (1+s) =)* < OPP(PP) < (1+ e)+ We proceed by induction.
For i = and ACE = =P" by Lemma B.3 we find an (E", (f..n/4k)-robuutt center, which we can label Ej without loss of generality. Let Ci denote the set of points in B(ef" 4(1 + +2) n AC According to Lemma B.2 we have (ET n ACC" = ej S ef" Therefore, the optimal cluster ej, which was active before iteration i, becomes inactive in this iteration. The disjointedness invariant is vacuous for 1.
For > 1, assume that both invariants holds for the clusters found so far. Since all points within distance 4(1 + +)f*+1 from the previous centers have been removed, the disjointedness invariant
IAC
continues to hold. There must exist active optimal cluster with at least
points. (If no
4[k-1
such cluster exists, the process terminates and nothing more needs be proven.) By
Lemma B.3 we
obtain an (E*, |ACf",1/4(k= -o-but center, which we can label by C. Define C.-
as B(c 4(1
n Then, by Lemma B.2 we have (C) Ac C ef" Thus, the optimal cluster Cj which was active before iteration i, becomes inactive this iteration. The disjointedness invariant also holds since filter all points within the desired radius.
30

---

Next, we prove that our invariants are respected at any time t, upon insertion or deletion of an arbitrary point p after invoking Algorithms CLUSTERINGINSERTION or CLUSTERINGDELETION respectively.
Lemma B.5. Suppose both of our invariants hold before time I. If an arbitrary point p is inserted or deleted af time I, both invariants will also hold after invoking Algorithm CLUSTERIING or CLUSTERINGDEEETTON
Proof. Let consider the disjointedness invariant first. The deletion of a point cannot violate it. For the case of insertion, we assign the newly inserted point to the lexicographically smallest cluster that contains it (if any), which ensures disjointedness.
For the closeness invariant, the insertion of a point cannot violate In the case of a deletion of a point at distance at most 2(1 + +e)OPT(P) (P) from of. the counter m is updated and, if zero is reached, we recompute subsequent clusters using INIT. Since the invariant for clusters i' < i are not affected, the execution of INIT will establish the invariants again for cluster i and subsequent ones.
B.5 Runtime Analysis
Lemma B.6. The running time of Algorithm CLUSTTERING Ö(d(k LC
Proof. The algorithm consists of (k- iterations for fixed guess (1 + 2)". Each iteration
j = --....,k k takes Ö(dvk= foakkjjjj jAC,)) Lemma B.3 Therefore, the total computation is bounded by
Ō(d(k: - i)1.51AC5)
Lemma B.7. Consider sequence S of n possibly adversarial updates, and let P. be the point set obtained after applying the first updates. The amortized update time per operation is (d.2.5).
Proof. The total number of guesses L incurs only extra Õ(1) factor, so can consider an arbitrary L. Note that insertions are handled in Ö(dk) time and that if at any time the size of the point set is Okk-25),, then we can obtain a 2-approximation by computing all pairwise distances. When point is deleted, there are three possible cases.
p belongs to some cluster i and p within distance 2(1 e)--1 from its center, then mf will be decreased by one. If m > then the update time is Ö(d)). If mf 1, then the i-th cluster along with subsequent ones need to be reconstructed. Consider first cluster i = 1. We prove the amortized bound by induction on the number of robust centers w that are computed throughout the algorithm for cluster = For w 1, we obtain an (f. P.l/4k) centerpoint in Ö(d Te P:I) time as the first robust center and proceed to compute the remaining k clusters. The total computation cost of (dk. 1.5 P:l) can be amortized over the first P. insertions, resulting in (d charge. For the inductive step, we amortize the computation of the (w + 1)-th robust center at time t over two operations: (1) the decreases that m. experienced and (2) the updates that occurred between time tu+1 and time tw. when the computation of the w-th robust center occurred. Since the computation of the w-th centerpoint is amortized over updates prior to tw. it does not affect the amortization on subsequent updates. The total computation to amortize is ((dk-1.51 (1tt.aa) Now, recall that tw+1 tw 2 / by the robust center property, and observe that
IPtw <
|Pr
lu+11 byp
= O(K)+
1w+1
t. 1w-+1
tu
t.w
This means that the points who caused m to decrement receive charge of Ō(dk2.5) from cluster i 1. while all other points (which did not cause m drop) receive a charge of ((d) from cluster i=1. 1.
Consider now i 1. The induction proceeds in similar way. The amortization of the first robust center for the i-th cluster is straightforward. For the inductive step, we again amortize the computation of the (w 1) robust center of cluster > 1 at time f the decrements well updates that occurred between time tw+1 and time tw. It is worth noting that deletions of points from clusters
O hides the polynomial factors of e llogonn log 1!
31

---

j > i cannot affect mf at all, whereas deletions from clusters j < i can only positively affect m since they might reset it without additional amortization charges. Let M be the number of active points time bop at the beginning of iteration i. The total computation to amortize is Ōdd(k: i)1.5 ( 2 No /4(k - i) by the robust center property, and observe that
Now, recall that f tw
Now
bu+1 bo Ō - -k O(
+
1 tu
fu++1
tw
tw+1
the
Again, the points who caused mf to decrement receive charge of (dh:..5 from some cluster > while all other points (which did not cause m to drop) receive a charge of Ô(d) from any other cluster > 1. Since each point belongs to single cluster, it receives one charge of (dd22.5) from its own cluster, at most & - 1 charges of (d) from other clusters, and at most l charges of ((dk-.)) when cluster is created for the first time, proving the claimed amortized update time.
remains to discuss the case in which p does not belong to any cluster and it is deleted from the remainder set. If the invocation of CLUSTERING creates new robust center for some i, induction as before. If the new cluster was created for the first time, we can charge the insertions of those points. If the cluster previously had robust center, Finally, if the guess is too low and no cluster can be created, there a one-time charge (l2)) for running Lemma B.3 after which the computation is halted.
apply
the argument above.
32


Reviews:
[{"review_id": "s2Qnpba2tI", "reviewer": "Reviewer_LwQb", "summary": "In this paper, the authors study the problem of maintaining the diameter and k-center clustering under dynamic updates (addition/deletion of points) under the presence of an adaptive adversary. The authors propose fully dynamic algorithms that achieve a 2-approximation for the diameter problem and a $(4 + \\epsilon)$-approximation for the k-center clustering problem. A simple 2-approximation dynamic algorithm picks a random anchor point $p \\in P$ and maintains its furthest neighbor throughout updates, remains the best known in terms of both approximation and update time. In this work, the authors provide a significant improvement, by designing a 2-approximation algorithm with worst case update of $O(d^5)$ under adaptive adversaries. Their work introduces novel techniques such as robust representatives based on center points and de-amortization strategies to ensure worst-case update time guarantees.", "questions": "It would have been great, if the authors highlighted the intution behind their novel sampling to improve update time.", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\nThe theoretical claims are strong (improvements over both the approximation guarantee and worst-case update time) and the algorithm relies on highly non-trivial techniques. \n\nThe guarantees hold against an adaptive adversary that also has access to randomness of the algorithm, which is a significantly harder case.\n\n**Weaknesses**:\n\nThe authors heavily rely on a prior work to find the center point. Essentially these center points serve as the anchor points (from folklore).\n\nThe authors explain the role of adaptive adversaries, motivating it. Such an adversary model is common in the literature, and the writing could be improved to focus more on the overview of technical challenges.", "was_revised": true, "final_justification": "I'm happy with rebuttal response. As I asked for clarifying questions, I am keeping my score.", "rebuttal": "Thank you for your valuable feedback and for the time spent reviewing our paper. We are encouraged by your positive comments, in particular that our techniques are highly non-trivial and that the model considered is significantly harder. We address the main concerns and questions below.\n\n> It would have been great, if the authors highlighted the intuition behind their novel sampling to improve update time.\n\nThank you for suggesting to add the intuition behind our novel sampling technique. Our sampling mechanism runs in time $\\tilde{O}(\\min(k^2, \\sqrt{k}n))$ (see Lemma B.3). This enables a total running time of $\\tilde{O}(dk^{1.5}n)$ for the offline clustering algorithm (see Lemma B.6), and an amortized update time of $\\tilde{O}(dk^{2.5})$ for our dynamic algorithm under adversarial updates (see Lemma B.7). We explain the intuition behind this novel sampling method in the updated version of the paper. For completeness, we provide a summary here.\n\nRecall that the robustness (see Definition 4.1) of a point $x$ is defined as the fraction of points in the dataset $P$ that lie within a ball centered at $x$ of a given radius. A higher robustness implies that $x$ is a stronger candidate for a center, as it can serve effectively over a longer sequence of dynamic updates.\n\nTo estimate the robustness of sampled points efficiently, we take into account that there are $k$ clusters. We sample $\\tilde{O}(k)$ points and estimate the robustness of each by measuring the fraction of other sampled points lying within a ball of radius $2\\cdot OPT$ around it (where $OPT$ denotes the optimal clustering cost). This allows us to identify a robust point—i.e., one that covers the most sampled points—in time $\\tilde{\\Theta}(k^2)$. Note that since $OPT$ is not known in advance, we use a logarithmic number of guesses, one of which is guaranteed to be within a constant factor of the true $OPT$.\n\nThis robustness estimation mechanism is efficient for our dynamic algorithm when the number of clusters $k$ is relatively small, specifically when $k \\leq n^{2/3}$, yielding a total running time of $\\tilde{O}(k^2)$.\n\nWhen $k$ exceeds this threshold, we employ a different mechanism. In this case, we reduce the sample size to $\\tilde{O}(\\sqrt{k})$ and modify our robustness estimation strategy. Instead of testing the fraction of sampled points within radius $2\\cdot OPT$ around each sample point, we test the fraction of original points in $P$ that lie within such a ball.\n\nThere are two cases:\n\nCase 1: The largest $\\sqrt{k}$ clusters each have size at least $n/k$.\nIn this case, with high probability, each of these large clusters will be represented in the sample. Estimating robustness based on coverage of original points will allow us to identify robust centers from these clusters.\n\nCase 2: The remaining $k - \\sqrt{k}$ clusters collectively contain at most $n/t$ points, for some constant $t$ (e.g., $t = 4$).\nSince the large clusters contain at least $(1 - 1/t)n$ points, by the pigeonhole principle, there exists a cluster with at least $\\frac{n}{4\\sqrt{k}}$ points. Sampling $\\tilde{O}(\\sqrt{k})$ points uniformly at random ensures, with high probability, that at least one point from this large cluster is included. We can then test its robustness against the full dataset in time $\\tilde{O}(\\sqrt{k}n)$.\n\n\n> The authors heavily rely on a prior work to find the center point. Essentially these center points serve as the anchor points (from folklore).\n\nThere are two novelties in our dynamic algorithm for the diameter problem. The first is the connection we made between dynamic algorithms against adaptive adversaries and the concept of a center point.\nThe concept of a center point is known in computational geometry and machine learning; however, its role in making dynamic algorithms resilient to adaptive adversaries is new and has not been explored before. We think that bridging a connection between two different lines of research would be as interesting as developing new techniques for one line of research. It in fact shows that tools classical in one area may help improve achievements in other areas. The second novelty is the set of lemmas that prove that center points can be maintained in a dynamic setting. This includes Lemma 2.10 and 20.9, which show an α-center point of a point set lies inside the convex hull of that set, and Lemma 2.7, which shows a point inside the convex hull of a set P can encode useful information, such as a 2-approximation of the diameter of P.\n\n> The authors explain the role of adaptive adversaries, motivating it. Such an adversary model is common in the literature, and the writing could be improved to focus more on the overview of technical challenges.\n\nThere are different variations of adaptive adversaries in the literature. The model we consider in this paper is the strongest. We thought it would be good if we explained the differences between randomness-adaptive adversaries and the weaker version, the output-adaptive adversaries. In this way, it will be clear to the readers precisely what adversarial model we consider. However, you are right; the discussion is a bit long. In the updated version of our paper, we make this section more compact and expand the overview of our algorithm and the analysis. \n\n\nFinally, if you feel that our response has adequately addressed your major concerns, please, consider adjusting your score accordingly."}, {"review_id": "YchfXFGCLD", "reviewer": "Reviewer_EhRa", "summary": "The paper is about fully dynamic (allowing insertions & deletions) constant factor approximation algorithms for the diameter and k-center clustering of the input. \n\nMoreover the algorithms are robust against adversaries that have full knowledge of the past decisions and random bits used by the algorithm, which is argued to be the strongest model that admits constant factor approximations.\n\nThe paper combines in a clever way, simple online algorithm with recent advances in computational geometry and with classical robust statistics.\n\nthe algorithm for maintaining the diameter is super simple and uses in a clever way the robustness of so called Tukey centerpoints, i.e., points that lie *deeply* in the interior of the point set:\n\nAny point (not necessarily in the input) in the convex hull (CH) of the current set of points is a 2-approximation for the diameter (or 1-center). The computed centerpoint lies deeply in the CH and has the property that at least d^2 many points need to be removed before it may fall out of the CH.\n\nA caveat is that such points are relatively expensive to compute, in roughly d^7. But once computed, they may not fall out of the CH on insertions and since they remain valid 2-approximations for at least d^2 deletions. Thus, the amortized time is only about d^5. The calculations steps are additionally cleverly distributed over all steps to additionally de-amortize the algorithm.\n\nThe contributions are well compared to prior work in two tables covering dynamic k-center and diameter problems, respectively.", "questions": "* to what extent do you think can the approximation factor be improved? Any comments?\n\n* to what extent do you think can the update time be improved? Why do you state O(k^6) as being \"prohibitively large\" even for small $k$ for k-center while O(d^5) is good enough for the diameter?\n\n* for k-center, any ideas on reaching linear k dependence as in prior work while dealing with an adaptive adversary?\n\n* I'd like to see a more formal definition of the Definition 2.4 (Tukey Depth). The current one reads more like an informal description.\n\n* I'd like to see a citation of Tukey's original work. Some more or less recent contributions from the computational geometry community are present, but the classical statistical work should also be cited. Especially for such an important notion named after its inventor.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nthe paper is well written, and contains a good presentation of related work and comparisons to prior results in similar settings.\n\nsimplicity of the algorithms\n\nclever combination of algorithmic concepts with computational geometry and basic robust statistics.\n\n \nWeakness:\nThe update time is rather high, and even though previous algorithms had other caveats, and in particular did not work against adaptive adversaries, they had achieved $1+\\epsilon$ or $\\sqrt{2}$ approximation which is better than the presented 2-approx.", "was_revised": true, "final_justification": "I'd like to see this paper published at the current NeurIPS due to its originality in combining results from different fields. However, I also have slight reservations, because it is unclear whether the presented techniques can be improved to below the (folklore) 2-approximation  or to significantly better d-dependence. For this reason, I have not increased my rating any further.", "rebuttal": "Thank you for your valuable feedback and for the time spent reviewing our paper. We are glad that the simplicity of our algorithms is valued and that you find the combination of computational geometry with basic robust statistics clever. We address the questions below.\n\n> To what extent do you think the approximation factor can be improved? Any comments?\n\nWe believe this to be an excellent direction for future work. While we thought about improving the factor using ideas from Chan and Pathak, we were unable to adopt their techniques to our setting. On a high level, the key problem is that the algorithm relies on obtaining a set of anchor points which are all far from each other, whereas our techniques intuitively try to do the opposite since we look at the centroid of the datapoints. Currently, it is not clear whether these ideas can be merged and we suspect that improving the approximation factor would require an approach that is distinct from the prior work in the non-adaptive setting.\n\n> to what extent do you think the update time can be improved? \n\nSince a main bottleneck in the update time is the running time of the algorithm for finding centerpoints, we suspect that the poly(d) factor can be improved. Obtaining a time that does not depend on the complexity of finding a centerpoint is likely much more challenging and would require more complex techniques.\n\n> Why do you state O(k^6) as being \"prohibitively large\" even for small k for k-center while O(d^5) is good enough for the diameter?\n\nThe value of $d$ is generally assumed to be polylogarithmic in $n$ while no assumption is made on $k$. On a high level this is because at most log(n) dimensions are generally sufficient to capture the geometry of a dataset. Indeed, the Johnson–Lindenstrauss lemma shows any dataset of points in $R^d$ can be projected into a dataset in $R^{d’}$ where $d’ \\in \\Theta(\\log(n))$ while approximately preserving distances.\n\n> for k-center, any ideas on reaching linear k dependence as in prior work while dealing with an adaptive adversary?\n\nWhile we currently do not have any ideas for either obtaining a linear-time algorithm or establishing hardness, we suspect that obtaining such an algorithm would require substantially new techniques and may in fact be impossible. Indeed, the prior work of Bateni et al. for adaptive adversaries has an approximation ratio of $O(\\min\\{k, \\log(n/k)/\\log\\log(n) \\})$. This suggests that obtaining any constant factor approximation with linear update time is a challenging problem and would likely require substantially new techniques.\n\n> I'd like to see a more formal definition of the Definition 2.4 (Tukey Depth) … \n\nWe appreciate the suggestion to use a more formal definition for the Tukey Depth and to include a citation to Tukey’s original work. We provide a more formal definition below which we have included in the paper and have added the appropriate citation [1].\n\nGiven a point set $P = \\{p_1, \\dots, p_n\\} \\subset \\mathbb{R}^d$, the **Tukey depth** of a point $x \\in \\mathbb{R}^d$ with respect to $P$ is defined as:\n$\nd_P(x) = \\min_{\\|v\\|=1} \\sum_{i=1}^n \\mathbf{1} [v^\\top (p_i - x) \\ge 0 ]\n$\n\n[1] Tukey, John W. \"Mathematics and the picturing of data.\" In Proceedings of the international congress of mathematicians, vol. 2, pp. 523-531. 1975.\n\n\nFinally, if you feel that our response has adequately addressed your major concerns, please, consider adjusting your score accordingly."}, {"review_id": "0QOzEOG41M", "reviewer": "Reviewer_8vVV", "summary": "The paper presents two fully dynamic algorithms:\n* dynamic maintenance of a 2-approximation to diameter in O(d^5 log^3 n) worst case update time\n* dynamic maintenance of (4+epsilon)-approximate k-center in O(k^2.5 d poly(epsilon^-1, log n)) amortized update time\nHere, d is the dimension of the underlying Euclidean space, and n is the current number of points.\n\nBoth results hold against a strong notion of adaptive adversaries, called randomness-adaptive adversary: the adversary has access to the algorithm, all random choices and outputs of the algorithm up to that point. \n\nThe diameter result relies on finding an epsilon-robust representative point of pointset P - intuitively, a point x such that dist(x, P) stays a 2 approximation to diam(P) even after any epsilon*n changes to set P. Finding such a point guarantees that we do not need to recompute the representative (and hence the diameter) of the set too often, and that the algorithm is also independent of the exact updates chosen by the adversary. The computation of the representative point is reduced to a black-box algorithm for finding an alpha-centerpoint (for alpha=1/poly d). After epsilon*n deletions to P, we simply recompute the representative point from scratch. The deamortization of this algorithm uses a standard technique by Motwani and Raghavan (1999).\n\nThe k-center algorithm does the following for each “guess” (1+epsilon)^l of the size of the optimal solution OPT(P). In the first round, we sample some points from P, and choose a point out of these that has most of the remaining points at distance at most 2(1+epsilon)^l. The chosen center, together with its closest points, is then deleted from P, and we recurse on the remaining points. Intuitively, if our “guess” of OPT(P) was good, we only have k rounds, and hence choose k centers.", "questions": "Is there a possibility of deamortizing the k-center algorithm? I assume that the recursive nature of the algorithm might make this hard, but maybe one can make these rounds of choosing the centers less dependent on each other.\n\nSome minor comments about the presentation: \nTable 1 shows dependencies of d, while Table 2 doesn’t, making it a bit inconsistent.\nLine 65: these performance measures also apply to the diameter problem.\nLine 128: citation format issue\nLine 201: who see -> who sees\nLine 233: should be P\\in R^d", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* The paper is well written, easy to follow, and provides good intuition of the techniques used. Even simple results are proven in detail in the appendix, making the whole paper self-contained.\n* The literature overview is comprehensive, and the summary of techniques in other papers clearly highlights the contributions of this work.\n* The results hold for a strong notion of adaptive adversaries: the adversary has access to the algorithm, all random choices, and outputs of the algorithm up to that point. \n\nWeaknesses: \n* While the diameter result uses some novel techniques, I think paying a large polynomial dependency on dimension just for getting worst-case guarantees feels like overkill to me. \n* The k-center result is less novel technically, but shows a clear improvement in the dependency on the number of centers. To me, it would be interesting to get such a result for the 2+eps approx regime, which is known to be tight for this problem.\nSome minor comments (see Questions section).", "was_revised": true, "final_justification": "The paper studies a timely problem, achieves relevant results, and it's very well written. I recommend acceptance and look forward to reading the final version.", "rebuttal": "Thank you for your thorough feedback and for the time spent reviewing our paper. We appreciate your positive review and the helpful minor comments on the presentation. We answer your question below.\n\n> Is there a possibility of deamortizing the k-center algorithm? I assume that the recursive nature of the algorithm might make this hard, but maybe one can make these rounds of choosing the centers less dependent on each other.\n\nThanks for this very good question. It seems that the recursive nature of the algorithm mostly plays a role in the update time of the algorithm, causing an extra O(k) factor. The problem that we had with the deamortization was that we could not deamortize different guesses of OPT, as the ‘right’ guess might change multiple times during the course of the deamortization."}, {"review_id": "fbsHXkVPGK", "reviewer": "Reviewer_SCZU", "summary": "The paper tackles two classical geometric problems—maintaining the diameter and $k$-center clustering—over fully dynamic point sets in high-dimensional Euclidean space, under the strongest “randomness-adaptive” adversary model. \n\nThe main contributions are\n1. a 2-approximation algorithm for dynamic diameter (and minimum enclosing ball) with worst-case update time $O\\bigl(d^{5}\\log^{1.5}d\\log^{1.5}(n/\\delta)\\bigr)$, and\n1. a $(4+\\varepsilon)$-approximation for fully-dynamic $k$-center with amortized update time $k^{2.5}d\\cdot \\mathrm{poly}(\\varepsilon^{-1},\\log n)$, improving the previous $k^6\\cdot \\mathrm{poly}(d, \\varepsilon^{-1}, \\log n)$ bound. \n\nBoth results hinge on a novel use of $\\varepsilon$-robust centerpoints (Tukey-depth ≥ $\\Omega(1/d^2)$) to pick \"representative\" anchors that survive many deletions.\nThe diameter algorithm also employs a careful de-amortization step.", "questions": "N/A", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. Fully dynamic algorithms for the diameter problem against adaptive adversaries with any non-trivial\napproximation and worst-case $\\mathrm{poly}(d \\log n)$ update time were previously not known.\n1. The improvement in update time for fully dynamic, adaptive $k$-center seems significant.\n1. The robust centerpoint idea is clean and may be applicable in other settings.\n\n---\n\n### Weaknesses\n1. The $d^5$ update time may be impractical for high-dimensional settings.", "was_revised": true, "final_justification": "I believe the improvement in the results are significant and will be a nice contribution to NeurIPS.", "rebuttal": "Thank you for your valuable feedback and for the time spent reviewing our paper. We are pleased that you recognize the significance of our fully dynamic diameter algorithm and the improved update time for k-center. We're also glad that you found the robust centerpoint idea clean and broadly applicable."}]

Author rebuttal:

Meta-review: The main result is a 2-approximate fully dynamic algorithm for diameter in high dimensional R^d, under adaptive adversary. A secondary result about k-center is also obtained. 

The diameter/k-center in high dimension is a fundamental problem, and the adaptive adversary setting is also a popular topic. The ratio of 2 seems to be strong, albeit it is not justified if it is possible to do 1 + eps. The technique looks nontrivial to me. Other weaknesses include weaker bound for k-center (e.g., dependence on k and the ratio are large). The reviews are generally positive and most concerns are discussed and addressed during the rebuttal.

Overall, this is a solid paper that merits acceptance.
Decision: Accept (poster)