{"id":"692411a4-58e0-4595-89b0-bdce23ef5bd4","arxiv_id":"2504.16382","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"New constant-round, fully scalable MPC algorithms improve Euclidean k-center approximation to (2+ε) in low dimension and O(log n/log log n) in high dimension.","lead":"This paper designs massively parallel algorithms for Euclidean k-center clustering that work even when every machine has only a small amount of memory. In low dimension it achieves a (2+ε)-approximation in a constant number of rounds, and in high dimension it gives the first fully scalable constant-round algorithm with O(log n/log log n) approximation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"High-dimensional Theorem 1.3 depends on an unproven black-box (Lemma 6.8); if [CGJ+24, Thm 3.1] differs from its restatement, the O(log n/log log n) ratio is unsupported.","rationale":"I carefully read the low-dimensional chain (Lemma 3.1 → Lemma 4.1 → Theorem 1.1, and Lemma 3.1 → Lemma 5.1 → Theorem 1.2). The new geometric hashing Lemma 3.1 has a self-contained proof in Appendix A; the third property (∪_u U^∞_τ(f^{-1}(u)) ⊆ complement of L(z,2b)^d) is correctly derived via Claim A.2 and the separation property of (d−1)-faces. The local simulation argument in Lemma 4.7 correctly bounds the influence radius by O(d^{2.5})τ, and Lemma 4.8's packing bound uses Property 4.2 appropriately. The MDS averaging argument in §5 is also sound: the projection counting step |M^*∩(L^c−v^*)| ≤ Σ_i |proj_i∩\\hat L(j^*_i)| is justified because { \\hat L(j)} partition R (up to the notational typo equating \\hat L(0) with the complement of L(z,2b), which the subsequent equations make clear). The high-dimensional ruling set analysis (§6.1) is the most delicate part: Lemma 6.9's application of Claim 6.10 is valid, and the configuration/union-bound machinery in Lemma 6.12 correctly yields exp(−Ω(t log(t/log Λ))) for the sum of prefix probabilities. The only place where the argument is not self-contained is the invocation of Lemma 6.8, which is external. I agree with the reader's weakest_assumption that this is the most load-bearing point. However, since the paper clearly cites a published theorem and the rest of the proof is sound, this does not change the ACCEPT verdict; it is a standard external dependency that should be verified by the reader/referee.","tokens_in":35409,"tokens_out":56453,"duration_ms":458940,"concrete_test":"Independently consult the published version of [CGJ+24, Theorem 3.1] (ICALP 2024, LIPIcs) and verify: (1) the algorithm is deterministic; (2) the set A_P(p,τ) satisfies B_P(p,τ)⊆A_P(p,τ)⊆B_P(p,O(ε^{-1})τ) with no additional log n factor in the radius; (3) local memory is poly(d log n) and total memory is O(n^{1+ε} poly(d log n)) for arbitrary P. If the actual theorem has a randomized guarantee, a larger radius expansion, or a different total memory, re-derive Lemma 6.5 with that radius as βτ and check the final ratio; if the radius is cτ with c=ω(ε^{-1}), Theorem 1.3's ratio becomes O(c log n/log log n), which would weaken the headline claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1.3 (and Lemma 6.1) is built on Lemma 6.8, restated from [CGJ+24, Theorem 3.1]: a deterministic MPC primitive that, for every point p, computes min(h(A_P(p,τ))) for some set A_P(p,τ) with B_P(p,τ)⊆A_P(p,τ)⊆B_P(p,O(ε^{-1})τ), using local memory poly(d log n), total memory O(n^{1+ε} poly(d log n)), in O(log_s n) rounds. The paper does not prove or even sketch how this primitive is implemented; it is simply invoked in the proof of Lemma 6.1. The entire ruling-set analysis in §6.1 (sequence length and union bound) depends on each step having radius at most βτ with β=O(ε^{-1}) and on the size bound |A|≤Λ from Fact 6.4. If the actual [CGJ+24] theorem is randomized, or its approximate ball is only contained in B(p,O(ε^{-1} log n)τ) (e.g., if it is the union of buckets from Lemma 3.4, whose diameter is O(ε^{-1} d/log log n · τ) = O(ε^{-1} log n/log log n · τ) after JL), or if the total memory is O(n^{1+ε} d^{O(d)}) rather than poly(d log n), then the step radius and the ruling set parameter would both degrade, and Theorem 1.3's claimed O(ε^{-1} log n/log log n) ratio would not follow. This is the single most load-bearing assumption because the low-dimensional theorems have self-contained proofs (up to the cited geometric hashing from [CFJ+22]), while the high-dimensional result is the paper's main new claim for d=O(log n).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper designs fully scalable MPC algorithms for Euclidean k-center. In low dimension, it gives a (2+ε)-approximation using exactly k centers and a (1+ε,1+ε)-bi-criteria algorithm, both in O(log_s n) rounds, with local memory (Ω(dε^{-1}))^{Ω(d)} poly log n and total memory O(n poly log n (O(dε^{-1}))^{O(d)}). In high dimension, it gives an O(ε^{-1} log n/log log n)-approximation in O(log_s n) rounds with poly(d log n) local memory and O(n^{1+ε} poly(d log n)) total memory. The algorithms are obtained via reductions to geometric ruling-set and minimum-dominating-set problems; the low-dimensional results rely on a new geometric hashing construction (Lemma 3.1), while the high-dimensional result uses a preprocessing step based on consistent hashing followed by a one-round Luby-type procedure.","tokens_in":35798,"tokens_out":29834,"duration_ms":262753,"significance":"If correct, these are the first constant-round fully scalable MPC algorithms for Euclidean k-center with a (2+ε) approximation in low dimension, and the first fully scalable algorithm in high dimension, improving substantially over the previous super-constant-round, super-constant-approximation results. The low-dimensional proofs are essentially self-contained and the new geometric hashing lemma (Lemma 3.1), with its third property on τ-annuli, is a nontrivial technical contribution. The high-dimensional result is an interesting extension of one-round Luby's algorithm and the ruling-set analysis is a substantive new argument; however, it rests on a black-box approximate-ball MPC primitive restated from [CGJ+24].","major_comments":[{"comment":"The high-dimensional result Theorem 1.3 depends entirely on Lemma 6.8, restated as [CGJ+24, Theorem 3.1], but the manuscript gives no proof, proof sketch, or parameter-by-parameter derivation of this primitive. The claim is load-bearing: the ruling-set analysis in Fact 6.4 and Lemma 6.6 requires the approximate ball to satisfy A_P(p,τ) ⊆ B(p,O(ε^{-1})τ), the procedure to be deterministic, and the total memory to be O(n^{1+ε} poly(d log n)). If the actual theorem in [CGJ+24] provides only a ball with an extra log n factor in the radius, or a randomized procedure, or a larger memory bound, then the claimed O(ε^{-1} log n/log log n) approximation ratio does not follow. I recommend that the authors add an appendix proving Lemma 6.8 or at least deriving it from the cited theorem with all constants and resource bounds checked; as written, the high-dimensional contribution is not self-contained and cannot be fully verified from the manuscript alone.","section":"Section 6, Lemma 6.8 (and Theorem 1.3)"}],"minor_comments":[{"comment":"In the definition of Eext, the phrase \"x'_m passes the test in line 2\" appears to invert the stopping condition: the subsequent proof treats Eext as the event that the sequence extends, which requires x'_m not to be added by Algorithm 5; please correct the wording.","section":"Section 6.1, Lemma 6.9"},{"comment":"The displayed equality \"= |M^*| + Σ ...\" should be \"≤\", since the sum over u∈f_v(P) of |M^*∩f^{-1}(u)| is at most |M^*|, not equal to it.","section":"Section 5, equation (2)"},{"comment":"The sentence \"it can be observed that \\hat L(0) = L(z,2b)\" is inconsistent with the definitions: \\hat L(0) is a union of length-4b boundary intervals, whereas L(z,2b) is the complementary middle intervals; the intended statement is that \\hat L(0) equals the complement of L(z,2b).","section":"Section 5, after equation (5)"},{"comment":"The notation \"L(z,2b)^d\" is used both for the d-th Cartesian power and for its complement; please introduce a separate symbol (e.g., an overline) to avoid ambiguity.","section":"Section 3, Lemma 3.1 and Section 5"},{"comment":"Please clarify that the \"(2τ,γτ)-ruling set\" is obtained by invoking Lemmas 4.1 or 6.1 with threshold 2τ; the comment \"γ=2(1+ε)\" is correct only after this scaling.","section":"Section 7, Algorithm 7 line 5"},{"comment":"The upper-bound proof for one-round Luby's algorithm is presented as a sketch; since this is a secondary observation not used in the main theorems, either mark it explicitly as non-essential or expand it to a full proof.","section":"Appendix B.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is a strong contribution and the low-dimensional results appear correct and complete. My only substantive concern is the black-box reliance of the headline high-dimensional theorem on Lemma 6.8, whose exact parameters are essential; given the authors' co-authorship of [CGJ+24], I expect this is fixable by adding a derivation or a detailed self-contained proof. I would not want the paper rejected over this issue, but I do not think it should be accepted in its current form without the high-dimensional result being fully verifiable from the manuscript or from a precise, checked pointer to the prior theorem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Briefly: this is a real advance. The low-dimensional results are self-contained (modulo a published consistent-hashing construction) and give the first constant-round fully scalable MPC algorithm for Euclidean k-center with (2+ε) approximation, plus a (1+ε,1+ε) bi-criteria version. The high-dimensional result—first constant-round fully scalable algorithm with O(log n/log log n) approximation—is also new, but it leans on a black box, and that is the place to check before accepting.\n\nWhat the paper does well: the new third property of the geometric hash (Lemma 3.1) is proved in Appendix A and is what makes the low-dimensional MDS argument work with poly(d) instead of 2^{O(d)} in the exponent. The analysis of the one-round Luby variant (Lemmas 6.5–6.12) is intricate and, as far as I can tell, correct. The reductions from k-center to ruling sets and MDS are standard but the paper integrates them cleanly with the new MPC primitives. The comparisons to prior work are fair.\n\nSoft spots, in proportion: Theorem 1.3 rests entirely on Lemma 6.8, a restatement of [CGJ+24, Theorem 3.1] that is invoked without proof. If the actual theorem is randomized, or if its approximate ball is only contained in B(p, O(ε^{-1} log n)τ), or if the total memory is O(n^{1+ε} d^{O(d)}), then the O(log n/log log n) ratio does not follow. I have not checked the source. This is the single load-bearing assumption for the high-dimensional claim. A referee must verify it. Everything else is minor: Appendix B is explicitly a sketch, and there are a few typos (e.g., the complement notation in Section 5). The low-dimensional theorems do not inherit this risk.\n\nWho should read it: anyone working on MPC clustering, distributed k-center, or geometric hashing. It deserves a serious referee and, with the black box verified, likely acceptance. My recommendation: send it out, but ask the referee to verify Lemma 6.8 against [CGJ+24] before endorsing Theorem 1.3.","headline":"Genuine advance for fully-scalable MPC k-center in low dimension; the high-dimensional claim should be checked against its black-box dependence.","tokens_in":36385,"tokens_out":4189,"would_cite":true,"duration_ms":38431,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","68W20","68U05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes the first constant-round fully scalable MPC algorithms for Euclidean k-center, achieving (2+ε)-approximation with exactly k centers in low dimension and O(log n/log log n)-approximation in high dimension.","keywords":["k-center","Massively Parallel Computation","fully scalable algorithm","ruling set","minimum dominating set","geometric hashing","consistent hashing","Euclidean clustering"],"falsifier":"Try to implement Lemma 6.8 with the exact ball $A=B(p,\\tau)$ on a dataset in $d=O(\\log n)$ whose $\\tau$-balls have large overlap; if the min-label query requires local memory $\\omega(\\operatorname{poly}(d\\log n))$ or total memory $n^{1+\\omega(\\varepsilon)}$, the high-dimensional guarantee collapses. Separately, for low dimension, compute the hash buckets of Lemma 3.1 for $d=2$, $\\beta=\\tau=1$, and check whether any point of any bucket's $\\tau$-annulus lies in $L(z,2b)^2$; a single such point falsifies Lemma 3.1.","tokens_in":35201,"feed_emoji":"📍","tokens_out":11744,"duration_ms":98363,"temperature":0.7,"pith_summary":"This paper claims the first constant-round fully scalable MPC algorithms for Euclidean $k$-center, in both the low- and the high-dimensional regime. In low dimension it achieves a $(2+\\varepsilon)$-approximation using exactly $k$ centers, and a bi-criteria $(1+\\varepsilon)$-approximation using $(1+\\varepsilon)k$ centers, each in $O(\\log_s n)$ rounds with local memory $(\\Omega(d/\\varepsilon))^{\\Omega(d)} \\operatorname{poly}\\log n$ and total memory $O(n \\operatorname{poly}\\log n \\cdot (O(d/\\varepsilon))^{O(d)})$. In high dimension it gives the first fully scalable MPC algorithm, an $O(\\varepsilon^{-1} \\log n/\\log\\log n)$-approximation, with $\\operatorname{poly}(d\\log n)$ local memory and $n^{1+\\varepsilon} \\operatorname{poly}(d\\log n)$ total memory. These results improve on earlier fully scalable algorithms that needed super-constant rounds, returned $k(1+o(1))$ centers, and worked only for constant dimension.","feed_headline":"MPC k-center: constant rounds, (2+ε) approximation","feed_subtitle":"Fully scalable machines now solve Euclidean k-center in constant rounds, close to the 2-approximation optimum.","key_machinery":"The load-bearing object is a geometric hash function $f:\\mathbb{R}^d\\to\\mathbb{R}^d$ (Lemma 3.1) with three properties: each bucket has diameter $\\ell=O(d^{1.5}\\beta)$; the buckets can be partitioned into $d+1$ groups whose distinct buckets are at $\\ell_\\infty$-distance greater than $\\beta$; and the union of all bucket $\\tau$-annuli avoids the periodic grid complement $L(z,2b)^d$. This hash turns the whole space into small, locally decoupled cells; any set of $\\ell_\\infty$-diameter at most $\\beta$ meets at most $d+1$ buckets, so in low dimension every MIS or MDS decision depends on at most $(d/\\varepsilon)^{O(d)}$ points that fit on a single machine. In high dimension the machinery is a $(\\Gamma,\\Lambda)$-consistent hash (Lemma 3.4), a hash under which any small-diameter set intersects few buckets, with $\\Lambda=\\operatorname{poly}(\\log n)$; after preprocessing, one-round Luby's is analyzed by an assignment sequence whose extension probabilities multiply to an $O(\\log n/\\log\\log n)$ domination bound.","core_discovery":"The paper's central claim is that Euclidean $k$-center can be solved by fully scalable MPC algorithms through geometric ruling sets and minimum dominating sets, with the Euclidean structure supplied by hashing. A $\\tau$-independent set of size at most $k$ is a valid center set once $\\tau\\ge 2\\,OPT$, so a $(2\\tau,\\gamma\\tau)$-ruling set yields a $\\gamma$-approximation; symmetrically, a $(1+\\varepsilon)$-approximate $\\tau$-minimum dominating set yields a $(1+\\varepsilon,1+\\varepsilon)$ bi-criteria solution. In low dimension a new geometric hash splits $\\mathbb{R}^d$ into buckets of diameter $O(d^{1.5}\\tau)$ organized into $d+1$ groups that are $\\tau$-separated inside each group; each bucket's maximal independent set or dominating set can then be computed on one machine, because only $(d/\\varepsilon)^{O(d)}$ nearby points are relevant. In high dimension, consistent hashing preprocesses the point set so that every $\\tau$-ball among representatives has size $\\operatorname{poly}(\\log n)$, and a one-round Luby-style algorithm with a random assignment sequence provably dominates every point within $O(\\varepsilon^{-1}\\log n/\\log\\log n)\\tau$ steps, improving on the $\\Theta(\\log n)$ that one-round Luby's achieves on general graphs.","pith_inferences":["The $d+1$-group hash is a generic local-decoupling device; a natural extension is to use it for other Euclidean bottleneck problems solvable by greedy local elimination, since only its first two properties are used for MIS while the third serves MDS.","The high-dimensional analysis suggests a transferable statement: one-round Luby's on any point set with $\\operatorname{poly}(\\log n)$-bounded $\\tau$-neighborhoods gives $O(\\log n/\\log\\log n)$-ruling sets, whereas on general graphs it is $\\Theta(\\log n)$; the improvement comes from bounded neighborhoods, not from the Euclidean metric itself.","For the MDS algorithm, replacing the exhaustive enumeration of $(d/\\varepsilon)^{O(d)}$ hash shifts by a random shift could reduce total memory at the cost of a probabilistic guarantee; the paper does not explore this trade-off."],"forward_implications":["For local memory $s=n^\\sigma$ with constant $\\sigma\\in(0,1)$, the low-dimensional algorithms run in a constant number of rounds, matching the round complexity of summing $n$ numbers.","The $(2+\\varepsilon)$ ratio with exactly $k$ centers is essentially the best possible, since $2$-approximation is the sequential optimum for $k$-center.","The $(1+\\varepsilon,1+\\varepsilon)$ bi-criteria algorithm returns $(1+\\varepsilon)k$ centers, almost matching the information-theoretic minimum of $k$ centers, and is the first such fully scalable guarantee.","For $d=o(\\log n/\\log\\log n)$, the algorithms use $s\\ge n^\\delta$ local memory and $n^{1+o(1)}$ total memory, improving the previously studied parameter regime in both approximation ratio and round count.","In high dimension the $O(\\varepsilon^{-1}\\log n/\\log\\log n)$ ratio beats the $\\Omega(\\log n)$ distortion lower bound that tree-embedding approaches to high-dimensional clustering would face."],"supporting_citations":[{"why":"Constructs the consistent hash whose parameter tradeoff (Lemma 3.4) bounds bucket diameter and the number of buckets any small set intersects, feeding the high-dimensional preprocessing.","marker":"[CJK+22]"},{"why":"Provides the hash construction that Lemma 3.1 inherits in low dimension; the first two properties come from this construction and the third is proved here.","marker":"[CFJ+22]"},{"why":"Supplies Lemma 6.8, the MPC primitive that returns the minimum label in an approximate ball, which the high-dimensional ruling-set guarantee uses as a black box.","marker":"[CGJ+24]"},{"why":"Establishes the reduction from k-center to independent sets: a 2µ-independent set on P has at most k points once µ≥OPT, turning a ruling set into a center set.","marker":"[HS86]"},{"why":"Gives the Johnson-Lindenstrauss transform that reduces the dimension to O(log n) while preserving distances, a precondition for the high-dimensional algorithm.","marker":"[JL84]"},{"why":"Supplies the one-round randomized Luby template for maximal independent sets that the high-dimensional algorithm modifies by hashing and a stopping-time analysis.","marker":"[Lub85]"},{"why":"Provides the previous fully scalable low-dimensional k-center algorithm whose super-constant approximation, super-constant rounds, and k(1+o(1)) centers are improved by Theorems 1.1 and 1.2.","marker":"[CCM23]"},{"why":"Records the Θ(log n) ruling-set bound for one-round Luby's on general graphs, the baseline that the Euclidean preprocessing improves by a log-log n factor.","marker":"[Gha22]"},{"why":"Supplies the packing bound (Lemma 2.1) used to count grid points in a small ball, yielding the (ε^{-1}d)^{O(d)} local size bound in low dimension.","marker":"[Pol90]"}],"fun_headline_variants":["Constant-round MPC for (2+ε) k-center","Fully scalable k-center: (2+ε) in O(1) rounds","Euclidean k-center: first constant-round MPC","k-center on MPC: near-optimal in constant rounds","Scalable MPC k-center: (2+ε) with low memory"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The high-dimensional theorem treats Lemma 6.8 as a black box: an MPC routine that, for every point $p$, returns the minimum random label inside an approximate ball $A$ with $B(p,\\tau)\\subseteq A\\subseteq B(p,O(\\varepsilon^{-1})\\tau)$ in $O(\\log_s n)$ rounds using $\\operatorname{poly}(d\\log n)$ local and $n^{1+\\varepsilon}\\operatorname{poly}(d\\log n)$ total memory. If that primitive cannot be built with these guarantees, the $O(\\log n/\\log\\log n)$ claim fails.","fun_headline_variants_meta":{"raw":{"variants":["Constant-round MPC for (2+ε) k-center","Fully scalable k-center: (2+ε) in O(1) rounds","Euclidean k-center: first constant-round MPC","k-center on MPC: near-optimal in constant rounds","Scalable MPC k-center: (2+ε) with low memory"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000248,"raw_usage":{"total_tokens":1670,"prompt_tokens":1195,"completion_tokens":475,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":811,"completion_tokens_details":{"reasoning_tokens":386}},"tokens_in":811,"tokens_out":475,"duration_ms":4216,"temperature":1.0,"reasoning_tokens":386,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:05:56.192031+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Try to implement Lemma 6.8 with the exact ball $A=B(p,\\tau)$ on a dataset in $d=O(\\log n)$ whose $\\tau$-balls have large overlap; if the min-label query requires local memory $\\omega(\\operatorname{poly}(d\\log n))$ or total memory $n^{1+\\omega(\\varepsilon)}$, the high-dimensional guarantee collapses. Separately, for low dimension, compute the hash buckets of Lemma 3.1 for $d=2$, $\\beta=\\tau=1$, and check whether any point of any bucket's $\\tau$-annulus lies in $L(z,2b)^2$; a single such point falsifies Lemma 3.1.","supporting_citations":[],"review_version":1}