{"id":"1662585a-22e3-4103-8480-a66c903c46ee","arxiv_id":"2502.05888","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For Euclidean k-center with k=n^c, the paper gives an O(1)-approximation in near-linear time by building small coresets via a new efficient consistent hashing.","lead":"New coresets shrink large Euclidean k-center instances to size roughly k times a sublinear factor, letting a known approximation algorithm run in near-linear time when k grows like a power of n. The result is a step toward fast clustering in high dimensions, where product quantization and record linkage need large k.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main theorem hinges on an uncited-proof volume bound from [AKS14]; the exponent 2/3 in the coreset size depends on its r^{2/3} scaling.","rationale":"The reader's weakest_assumption is exactly the volume bound in Lemma 3.3. I agree. The proof of Lemma 3.2, and hence Theorem 1.1, depends on the bound vol([0,1]^d + B(0,r)) ≤ poly(d)·exp(O(d^{2/3} r^{2/3})) for r ≤ sqrt(d/(2π)). Substituting r = sqrt(d)/β gives tβ = poly(d)·exp(O(d/β^{2/3})), and after JL this is n^{O(1/β^{2/3})}. The near-linear claim for k = n^c requires this exponent to be < 1−c with β = poly((1−c)^{-1}), which works because 1/β^{2/3} decays polynomially. If the true volume bound had a weaker β-dependence (e.g., exp(O(d r)) instead of exp(O(d^{2/3} r^{2/3}))), then after JL the coreset size would be exp((log n)^{3/2}/β), which is super-polynomial for any fixed β and would break the near-linear claim. So the exact r^{2/3} scaling is essential. However, Lemma 3.3 is a standard, published result (AKS14, SICOMP), so the risk of it being false is low. The gap is that the paper imports the bound without proof; a reviewer can verify it from the original source or by a numerical/Steiner-formula check. The small-α gap (α < sqrt(2π)) is a separate minor flaw in the theorem's stated range, but it does not affect the main near-linear O(1) result for k = n^c, where α can be chosen large. Thus I agree with the reader's identification and keep the ACCEPT verdict.","tokens_in":15581,"tokens_out":50467,"duration_ms":438742,"concrete_test":"Independently re-derive Lemma 3.3 for C = [0,1]^d and r = sqrt(d)/β with β ≥ sqrt(2π). Use the Steiner formula vol(C ⊕ B(0,r)) = Σ_{j=0}^d C(d,j) ω_j r^j and numerically evaluate the sum for d = 50,100,200 and β = 3,10,100, checking it against poly(d)·exp(1.5 (2π)^{1/3} d^{2/3} r^{2/3}). Alternatively, consult [AKS14] Lemma 3.1 to confirm the statement and constants. If the bound is confirmed, the exponent 2/3 is sound; if it fails, recompute tβ and the coreset size.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 3.2's consistency bound tβ = poly(d)·exp(O(d/β^{2/3})) is the engine of Theorem 1.1. It is obtained by applying Lemma 3.3, a volume bound for the Minkowski sum of a unit cube and a ball, which is quoted verbatim from [AKS14] without proof. After the JL step (d = O(log n)), the coreset size becomes k·n^{O(1/β^{2/3})}, and the near-linear claim for k = n^c requires this exponent to be made < 1−c by choosing β = poly((1−c)^{-1}). The exact r^{2/3} scaling in the exponential of Lemma 3.3 is what produces the β^{2/3} decay; a different r-dependence (e.g., exp(O(d r)) would give exp((log n)^{3/2}/β), a super-polynomial coreset size, destroying the near-linear claim. Because Lemma 3.3 is not proved or derived in the paper, the main theorem is conditional on an external bound whose exact scaling is load-bearing. The bound is cited to a published SICOMP paper and is very likely correct, so this is a verification gap rather than a demonstrated error.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies Euclidean k-center in the large-k regime through α-coresets. It gives two coreset constructions: Theorem 1.1 builds an O(α)-coreset of size O~(k n^{1/α^{2/3}}) in O~(n) time using a new consistent-hashing construction based on a randomly shifted grid, and Theorem 1.2 builds an O(α)-coreset of size k polylog n in O~(n k^{1/α^2}) time using random sampling and approximate nearest neighbor search. Composed with the EHS20 approximation algorithm, these yield improved time-approximation trade-offs, including a near-linear-time O(1)-approximation whenever k = n^c for 0 < c < 1. The paper also contains an experimental evaluation of the Theorem 1.1 coreset on four real datasets.","tokens_in":15811,"tokens_out":18950,"duration_ms":186636,"significance":"The results are a meaningful step for k-center in the large-k regime: they remove the superlinear k-factor from Gonzalez's algorithm for k = n^c, and the consistent-hashing construction with polynomial-time evaluation is a clean and potentially reusable tool. The proofs are largely self-contained, with explicit constants in the covering lemmas and no fitted parameters or circular dependencies; the claimed trade-offs follow from concrete reduction arguments. I regard the central claims as sound and the main theorem as a significant advance, provided the small proof gaps identified below are repaired.","major_comments":[{"comment":"The tail argument counts ⌈log n⌉ successful halvings and then asserts that Q(j') is empty, but after ⌈log_2 n⌉ halvings a set can still have size 1, which is not empty; the argument needs ⌈log_2 n⌉+1 successful halvings. The same value L = 5⌈log n⌉ and the binomial tail bound with m+1 still give failure probability below 1/n, so this is a local repair, but it is necessary because Lemma 5.2 is the key correctness lemma for Theorem 1.2.","section":"Section 5, Lemma 5.2"}],"minor_comments":[{"comment":"The exponent 2/3 that drives the coreset size in Theorem 1.1 is imported from the volume bound of [AKS14] without proof; since the near-linear claim for k = n^c depends on this exact r^{2/3} scaling, I suggest including a proof or a short self-contained derivation in an appendix to make the dependency transparent. I consider this a verification gap rather than a detected error.","section":"Section 3, Lemma 3.3"},{"comment":"The proof writes f : R^d → R^{d'} after invoking the JL lemma, but Lemma 4.3 only provides f : P → R^{d'}; the subsequent argument is valid using f on P alone, and injectivity on P follows from (1−ε) > 0, so the notation should be adjusted.","section":"Theorem 1.1 proof"},{"comment":"Lemma 3.2 is stated for β ≥ √(2π), while Theorem 1.1 is stated for every α ≥ 1; the proof should explicitly set β = max(α, Θ(1)) so that the O(α) notation absorbs the constant regime.","section":"Lemma 3.2 / Theorem 1.1"},{"comment":"The diameter condition should quantify over points in the image of φ; for y outside the range, φ^{-1}(y) is empty, so the current wording is slightly imprecise.","section":"Definition 3.1"}],"recommendation":"minor_revision","confidential_remarks":"The off-by-one in Lemma 5.2 is entirely local and can be fixed without changing the theorems; I would be comfortable with acceptance after that correction. The dependence on the AKS14 volume bound should be made more explicit in the revision, but I have no reason to doubt its validity."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Good paper, worth refereeing. The headline result—near-linear time O(1)-approximation for Euclidean k-center when k=n^c—is real, and the machinery is clean. The new consistent hashing (Lemma 3.2) is the centerpiece: a randomly shifted grid that gets Lambda = poly(d)·exp(O(d/beta^(2/3))) with O(d) evaluation time, beating previous polynomial-time constructions on parameter trade-offs. The coreset theorems follow from a simple covering argument, and the reduction via Lemma 2.2 and JL is standard. I checked the proofs of Lemmas 3.2, 4.2, 4.5, and 5.2; they hold up. The experiments are honest and show 2–4x speedup over Gonzalez with modest cost increase; not the paper's main value but not window dressing either.\n\nSoft spots, in order of severity:\n\n1. The load-bearing volume bound (Lemma 3.3, quoted from [AKS14]) is imported without proof. The exponent 2/3 in t_beta comes directly from the r^(2/3) scaling in that bound. If the true scaling were different, the coreset size would degrade and the near-linear claim could collapse. The bound is cited to a published SICOMP paper and is very likely correct, so this is a verification gap rather than a demonstrated error. Still, the authors should include a proof sketch or a precise pointer to the exact lemma in [AKS14], because the main theorem depends on that specific scaling.\n\n2. Minor: the tail bound in Lemma 5.2. The argument counts successful halvings until Q is empty; as written it should require ceil(log_2 n)+1 successes, not the stated count, to guarantee emptiness. The bound still goes through with L = 5 ceil(log n), but the counting is off by one.\n\n3. The JL step in Theorem 1.1 is slightly implicit. Injectivity of f on P and the opt(P') <= 2(1+epsilon)opt(P) claim are asserted rather than spelled out. They follow from standard arguments.\n\nThe citation pattern is fine. Self-citations are contextual and do not feed circularly into the claims. No fitted parameters appear; the guarantees come from derived covering lemmas.\n\nWho is this for? Anyone working on k-center, coresets, or high-dimensional geometric hashing. It advances the large-k trade-off without resolving the full problem (O(1)-approximation in near-linear time for all k). I would bring it to reading group and cite it. Send it to serious referees; the gaps are fixable. My recommendation: accept after minor revision, with the authors asked to prove or more precisely cite the volume bound.","headline":"Solid, accept-worthy theory paper with a real advance for large-k Euclidean k-center; the main caveat is a load-bearing external volume bound that is cited but not proved.","tokens_in":16420,"tokens_out":2003,"would_cite":true,"duration_ms":18419,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68U05","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that Euclidean k-center admits an O(α)-coreset of size O~(k n^{1/α^{2/3}}) computed in near-linear time, yielding an O(1)-approximation for k=n^c.","keywords":["k-center","coreset","consistent hashing","randomly shifted grid","Euclidean clustering","approximation algorithms","large-k regime","near-linear time"],"falsifier":"Directly evaluate the volume of [0,1]^d ⊕ B(0,r) for r=$\\sqrt$(d)/β at, say, d=500 and β=2 by Monte Carlo integration; if the log-volume grows faster than Θ(d/$β^{{2/3}}$)—or equivalently, if a randomly shifted unit grid is hit by many more than exp(O(d/$β^{{2/3}}$)) cells—then Lemma 3.2's parameter bound fails and the coreset size theorem does not follow.","tokens_in":15381,"feed_emoji":"🎯","tokens_out":8901,"duration_ms":75967,"temperature":0.7,"pith_summary":"This paper tries to establish that the Euclidean k-center problem can be solved to a constant approximation in near-linear time even when the number of centers k is as large as n^c for any 0<c<1, by first compressing the n-point input into a much smaller 'coreset'. Its main theorem gives an O(α)-coreset of size O~(k $n^{{1/α^{2/3}}$}) constructible in O~(n) time, meaning any β-approximation computed on the coreset is an (α+β)-approximation on the full data. For k = n^c, setting α = poly(1/(1-c)) yields an O(1)-approximation in near-linear time, improving the previous O($n^{{1+1/α^2}}$)-time trade-off. Experiments on four real datasets show the coreset-accelerated greedy 2-approximation algorithm runs 2 to 4 times faster than on the full data while keeping cost within about 1.3 times.","feed_headline":"Coresets give near-linear O(1)-approx for large-k k-center","feed_subtitle":"A randomly shifted grid shrinks the data to k·o(n) points, speeding up greedy 2-approximation clustering by 2–4x in tests.","key_machinery":"The central object is the (Γ,Λ,ℓ)-consistent hashing of Definition 3.1: a distribution over maps φ: R^d → R^d such that each cell $φ^{{-1}}$(x) has diameter at most ℓ and the expected number of cells intersecting any ball of radius ℓ/Γ is at most Λ. The paper constructs one by a uniformly randomly shifted integer grid, φ(x) = ⌊x+v⌋, and proves the bound Λ = poly(d)·exp(O(d/$β^{{2/3}}$)) from a volume bound on a unit cube inflated by a ball. This hash turns each optimal cluster—a ball of radius opt—into at most Λ cells, so one representative per nonempty cell is a covering of size kΛ; after projection to O(log n) dimensions, the size becomes k $n^{{O(1/α^{2/3}}$)}. The companion machinery is the covering-to-coreset reduction, which says a (β·opt)-covering is a β-coreset.","core_discovery":"On its own terms, the paper establishes that approximation-preserving data reduction for k-center can be done by finding a small covering: a subset S of P such that every point is within O(α·opt) of S, because any β-approximation on such an S is an (α+β)-approximation on P. The main construction is a new consistent hashing based on a randomly shifted grid: with parameter β, every ball of radius $\\sqrt$(d)/β intersects only poly(d)·exp(O(d/$β^{{2/3}}$)) grid cells in expectation, evaluable in O(d) time—the first polynomial-time consistent hashing with this trade-off. Composed with a random projection to O(log n) dimensions, this yields the near-linear coreset of Theorem 1.1; a separate sampling argument with approximate nearest neighbors yields the k·polylog(n)-size coreset of Theorem 1.2 in O~(n $k^{{1/α^2}}$) time.","pith_inferences":["The new consistent hashing is likely useful beyond k-center: any high-dimensional geometric algorithm that relies on sparse partitions can now use a randomly shifted grid with polynomial-time evaluation instead of an exponential-time construction.","The near-linear guarantee depends on reducing dimension with a random projection; without that step the coreset size carries an exp(d/β^{2/3}) factor, so the approach does not remove the exponential dependence on dimension in the coreset size.","A natural testable conjecture is that the exponent 2/3 in the coreset exponent is tight for this construction, since it comes directly from the inflated-cube volume bound rather than from an information-theoretic argument."],"forward_implications":["Running the known O(n^{1+1/α^2})-time O(α)-approximation algorithm on the Theorem 1.1 coreset gives an O(α)-approximation in O~(n + k^{1+1/α^2} n^{O(1/α^{2/3})}) time, improving the previous running time.","For k = n^c with 0<c<1, the coreset yields a near-linear-time O(1)-approximation algorithm for Euclidean k-center.","The Theorem 1.2 coreset gives an O(α)-approximation in O~(n k^{1/α^2}) time with coreset size k·polylog(n).","Because the coresets are coverings, they compose and reduce, so they fit into merge-and-reduce schemes for streaming, dynamic, and distributed clustering.","Experiments show the coreset-accelerated greedy 2-approximation is up to 4 times faster with cost within about 1.3 times on four real datasets."],"supporting_citations":[{"why":"Supplies Lemma 3.3, the volume bound on a unit cube inflated by a ball, which sets the 2/3 exponent in the consistent-hashing parameter.","marker":"[AKS14]"},{"why":"The O(n^{1+1/α^2})-time O(α)-approximation algorithm that the coresets are designed to speed up.","marker":"[EHS20]"},{"why":"Supplies the classical 2-approximation greedy algorithm used as the experimental baseline and as a building block in the dimension-reduction argument.","marker":"[Gon85]"},{"why":"The random-projection lemma used to reduce the input to O(log n) dimensions so the coreset size becomes k n^{O(1/α^{2/3})}.","marker":"[JL84]"},{"why":"Approximate nearest neighbor structure used by the sampling-based covering of Theorem 1.2.","marker":"[AI06]"},{"why":"Introduced the consistent-hashing framework in Euclidean space; the new hash improves its evaluation time from exp(d) to poly(d).","marker":"[CFJ+23]"}],"fun_headline_variants":["Data reduction gives near-linear O(1)-approx for large-k k-center","Coresets shrink data to k·o(n) points for faster k-center","Random shifted grids yield near-linear-time k-center coresets","Coresets make Gonzalez k-center up to 4x faster"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof leans on an imported volume bound—that inflating the unit cube by a ball of radius r increases its volume only by a factor exp(O($d^{{2/3}}$$r^{{2/3}}$))—and if that bound's exponent is actually larger, the coreset size grows faster with the approximation parameter and the near-linear regime would require a worse trade-off.","fun_headline_variants_meta":{"raw":{"variants":["Data reduction gives near-linear O(1)-approx for large-k k-center","Coresets shrink data to k·o(n) points for faster k-center","Random shifted grids yield near-linear-time k-center coresets","Coresets make Gonzalez k-center up to 4x faster"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000826,"raw_usage":{"total_tokens":3616,"prompt_tokens":954,"completion_tokens":2662,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":2584}},"tokens_in":570,"tokens_out":2662,"duration_ms":18682,"temperature":1.0,"reasoning_tokens":2584,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T17:33:54.191826+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Directly evaluate the volume of [0,1]^d ⊕ B(0,r) for r=$\\sqrt$(d)/β at, say, d=500 and β=2 by Monte Carlo integration; if the log-volume grows faster than Θ(d/$β^{{2/3}}$)—or equivalently, if a randomly shifted unit grid is hit by many more than exp(O(d/$β^{{2/3}}$)) cells—then Lemma 3.2's parameter bound fails and the coreset size theorem does not follow.","supporting_citations":[],"review_version":1}