{"id":"4c74c305-3d61-415e-adf7-655f9a86483c","arxiv_id":"2611.17050","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Fully dynamic diameter approximation below sqrt(2) is maintained with update exponent 2/c^2-1 and an exactly sqrt(2) endpoint with poly(d, log n) updates, via a lifted-centerpoint variance identity.","lead":"This paper gives faster dynamic algorithms for maintaining an approximate diameter pair of points in high-dimensional Euclidean space under insertions and deletions. It improves the classic Indyk bounds by lowering the update and space exponents through a new variance-augmented centerpoint technique.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"The load-bearing step is the 'one event for all adaptive queries' union bound in Section 6.1: if its per-copy cap events do not compose as stated, an exposed filter family can break the worst-case guarantee of Theorem 1.1.","rationale":"I read the paper as trying to prove that the dynamic diameter exponents below sqrt(2) survive an adversary who sees every previous random choice. The geometric heart—variance-augmented centerpoint, deterministic witness halfspaces in Lemma 5.1, first-core assignment, and the angular separation in Lemma 5.6—is internally coherent, and the reader's algebraic spot checks match my own reading of the displayed formulas. The single place where the adaptive guarantee could fail is therefore not the geometry but the assertion in Section 6.1 that one event covers all future queries, subsets, and acceptance predicates. If that assertion is true, Section 7.3's conditional union bound over a polynomial number of events gives the theorem; if it is false, the exposed-randomness model is not actually supported. I could not find a specific false step: the direction-net rounding, reserved margin e/8, amplification copies, and caps all appear to line up. But the per-copy event is described rather than exhibited, so the paper's condition for acceptance should remain independent verification of that step, consistent with the reader's CONDITIONAL verdict. I recommend no change to the verdict: the concern is real but not demonstrated, and the construction has enough independent support—deterministic certificates, checked algebra, and explicit schedules—that REJECT would be unjustified without a concrete counterexample.","tokens_in":52593,"tokens_out":23037,"duration_ms":158994,"concrete_test":"State the per-copy event of Lemma 6.3 explicitly as a predicate on one copy's random caps: target p has at most 100(E_u + 1) tuples, query q has at most 100(E_q + 1) tuples, shared nonpositive-correlation occurrences are at most 100(E_q + 1), and p shares a base cap in every family. Then compute the failure probability of the r-copy union bound over the direction net and the m birth targets, verifying that all constants are uniform in the net direction and in x in [h,1]. If the supplied Lean repository does not already cover this lemma, formalize exactly this event and union bound; a completed machine-checked proof settles whether the adaptive claim holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1.1's exposed-randomness guarantee is assembled in Section 6.1 ('One event for all adaptive queries') and Section 7.3 ('One failure budget'). For each frozen birth pool, Lemma 6.3 must supply one success event that is simultaneous over the direction net of mesh eta/(8 ceil sqrt d), all m birth targets, every later subset of the pool, and every compatible exact acceptance predicate. The proof amplifies with r = O(log(m/eps0) + d log(d/eta)) independent copies and union-bounds over the net and the m targets. The text does not write out the per-copy event as an explicit predicate on the Gaussian caps. In particular, the target-list cap is target-specific, while the query-list and rejected-occurrence caps are query-specific; the union bound treats their failure probabilities as uniformly constant under the same coupling. If conditioning on the query cap shifts the target-cap probability, or if the constants are not uniform over the direction net, the single event could fail with probability larger than the allocated budget. Because the adversary sees all previous random choices, one unlucky filter family in one generation would then destroy the worst-case update bound rather than add a logarithmic factor. This is an auditability gap, not an observed contradiction; the arithmetic of the union bound is consistent on its face.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper presents a fully dynamic data structure for maintaining a factor-c approximate Euclidean diameter under point insertions and deletions, for any fixed 1 < c < sqrt(2). The main result (Theorem 1.1) achieves worst-case update time n^{2/c^2 - 1} poly(d, log n) and space n^{2/c^2} poly(d, log n), improving on Indyk's earlier bounds. The construction also yields a sqrt(2)-approximation with polylogarithmic update time, a time-space tradeoff near linear space, and static diameter and farthest-neighbor algorithms. The technical core combines a lifted centerpoint that records variance, a reduction of the search to a common angular gap, and locality-sensitive filtering with explicit or implicit incidence representations. The guarantees hold against an adaptive adversary that sees all previous random choices.","tokens_in":52898,"tokens_out":3511,"duration_ms":22729,"significance":"If correct, the results represent a substantial improvement over the state of the art for dynamic diameter in high dimensions. The update exponent 2/c^2 - 1 is strictly smaller than Indyk's 1/c^2 for all c in (1, sqrt(2)), and tends to zero as c approaches sqrt(2). The space exponent is also improved. The sqrt(2) endpoint with polylogarithmic update time is particularly clean. The technical machinery—variance-augmented centerpoints, common angular gap reduction, and certified implicit inversion—is novel and likely to be influential. The paper also provides lower bounds under the randomized OVC and an INDEX-based memory lower bound, contextualizing the results. The static corollaries improve on recent work by Andoni–Jiang–Zharkov. The paper is thorough, with detailed proofs and explicit parameter choices.","major_comments":[{"comment":"The argument that a single success event holds simultaneously for every query direction, every subset of the birth pool, and every compatible acceptance predicate is load-bearing for the adaptive guarantee. The proof uses a finite direction net of mesh eta/(8 ceil sqrt d) and amplifies with O(log(m/eps0) + d log(d/eta)) independent copies, then union-bounds over the net and the m birth targets. However, the per-copy event is not written out as an explicit predicate on the Gaussian caps. In particular, the target-list cap is target-specific, while the query-list and rejected-occurrence caps are query-specific; the union bound treats their failure probabilities as uniformly constant under the same coupling. If conditioning on the query cap shifts the target-cap probability, or if the constants are not uniform over the direction net, the single event could fail with probability larger than the allocated budget. The arithmetic of the union bound is consistent on its face, but the lack of an explicit per-copy predicate makes this step less mechanically verifiable than the rest of the paper. The authors should either write out the per-copy event explicitly or provide a more detailed justification that the three caps (target, query, rejected-occurrence) can be union-bounded with the same coupling without hidden dependencies.","section":"Section 6.1, Lemma 6.3 and the paragraph 'One event for all adaptive queries'","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The certified finite families rely on a finite test that checks coverage on a net of the small sphere. The proof that a random family passes this test with constant probability uses Gaussian tail estimates and a union bound over net pairs. However, the test also requires that the sampled Gaussian vectors have bounded norm (cap G) and that the finite-precision coefficients are close enough to ideal Gaussians. The authors argue that these events hold with probability 1 - o(1) and that the coupling error is smaller than the reserved margin. This is plausible, but the argument is spread across Appendix B and the main text, and the exact margin accounting is not fully closed. In particular, the net error nu = b^{-2}, the norm cap G = O(sqrt(log m)), and the threshold margin 2G nu are said to be less than 1/t0. The inequality G nu t0 = O(ell^{-1/2} L^{-zeta}) = o(1) is asserted, but the constants depend on c and sigma and are not explicitly verified. Given that this construction is central to the zero-error tradeoff, the authors should provide a self-contained verification that the reserved margin (h - 3epsilon) is sufficient to absorb all finite-precision errors, with explicit inequalities.","section":"Section 6.2, Proposition 6.4 and Appendix B","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The failure budget is allocated by assigning conditional failure probability delta / S^{C1} to each relevant event, where S = n + t + d + B + ceil(log(2/delta)) + 2. The number of events is polynomial in S, so a union bound gives total failure probability at most delta. However, the events include 'center constructions, filter constructions, verification attempts, and witness samples.' The paper does not provide an explicit count of how many such events occur in the worst case. The number of center constructions is bounded by the replacement schedule (polynomial in alpha^{-1} log n), and the number of filter constructions is bounded by the frozen-interval schedule (logarithmic in t). But the number of witness samples per node is O(alpha^{-1} log(1/psi)), and psi is set to delta / (something). The total count could be as large as poly(n, t, d, B, log(1/delta)). The authors should either give an explicit polynomial bound on the number of events or argue that the union bound works with a sufficiently large constant C1 without enumerating all events. As written, the argument is plausible but incomplete.","section":"Section 7.3, 'One failure budget for the whole execution'","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The lemma states that the optimizer satisfies a + 4v <= Lambda_h(sigma) and that v < 1/16, so the inverse restriction 3v + 6eta < 1 + a holds with margin. The proof uses algebraic manipulation and the specific values of the optimizer. However, the verification that a + 4v <= Lambda_h(sigma) relies on the inequality Lambda_h(sigma) - (a + 4v) = (1+sigma)(chi_h - 5a_h) + sigma > 0 for sigma <= u_h, and for sigma >= u_h it uses u = sigma, kappa = 1, a = sigma, v = 0. The expression a_h = u_h/(1+u_h) and the inequality a_h/chi_h < 1/12 are stated without derivation. The authors should provide a brief derivation or reference to the Rayleigh quotient calculation that justifies these inequalities. Without it, the claim that maintenance never exceeds the query exponent is not fully verified.","section":"Section 9.2, Lemma 9.2 and the implicit tradeoff","authors_acknowledge":null,"authors_acknowledge_p":null}],"minor_comments":[{"comment":"The abstract states 'n bounds the number of active points' but Theorem 1.1 uses n as an upper bound on |P|. This is consistent, but the notation should be clarified: n is a capacity, not the current size. The paper does this in Section 3, but the abstract could be more precise.","section":"Abstract and Section 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Figure 3(b) is described as a planar picture of the lift, but the points are one-dimensional. The caption says 'A planar picture of the lift' which is slightly misleading. Consider rephrasing to 'A one-dimensional example shown in the plane' or similar.","section":"Section 2.1, Figure 3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The lemma states 'If V = 0 or R_S > K sqrt(V), then D_C < cL unless D_C = L = 0.' The proof uses the triangle inequality and the fact that 1 + 1/K < c. However, the condition R_S > K sqrt(V) does not guarantee that R_S > 0; if V = 0 and R_S = 0, then D_C = 0 and L = 0, which is handled. The proof should explicitly note that when V = 0, every core point equals o, so D_C <= R_S <= L, and the inequality D_C < cL holds unless L = 0. This is fine, but the wording could be clearer.","section":"Section 5.2, Lemma 5.3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The lemma states that the index has data work (m^u + m^{I_h(x)/ell}) P, query work (m^q + m^{I_h(x)/ell}) P, and space (m^{1+u} + m^{I_h(x)/ell}) P. The term m^{I_h(x)/ell} appears in all three bounds. It would be helpful to note that I_h(x) = 1 + u, so m^{I_h(x)/ell} = m^{(1+u)/ell}. Since ell is a fixed constant (>= 16/rho), this term is subpolynomial in m (specifically, m^{O(1/ell)}). The authors should clarify that this term is absorbed into the polynomial factor P, not into the exponent of m.","section":"Section 6.1, Lemma 6.3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The lemma states that the birth-pool interface gives a fully dynamic search index with the same time and space exponents, up to logarithmic factors. The proof sketch mentions that 'few indices coexist' and that 'there are at most three serving intervals of any given length.' This is correct, but the argument that the total space is n^{1+sigma} P relies on the fact that m^{1+sigma} <= n^{sigma} m. Since m <= n, this holds. However, the construction workspace for pending jobs must also fit the space bound. The authors should explicitly state that the workspace for a pending job is O(m^{1+sigma} P) and that the total over all pending jobs is O(n^{1+sigma} P) because the sum of birth sizes over pending jobs is O(n). This is implied but not stated.","section":"Section 7.1, Lemma 7.1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The corollary states that no single fully dynamic (1+epsilon)-diameter scheme can have initialization time n^K p(d, epsilon^{-1}, log(2nt)), expected amortized update time n^{1-gamma} p(d, epsilon^{-1}, log(2nt)), constant-time answer retrieval, and success probability at least 2/3 on each read, under randomized OVC. The quantifier order is important: K, p, gamma are fixed before epsilon is chosen. The proof uses Lemma 8.2 with s = 2 - gamma. However, the lemma requires that the update time is m^{alpha+o(1)} amortized, where alpha is the exponent of n in the update time. Here the update time is n^{1-gamma} p(...), which is n^{1-gamma+o(1)}. So alpha = 1 - gamma. Then s = max{1+alpha, beta} where beta is the answer-read exponent (0 for constant time). So s = max{2 - gamma, 0} = 2 - gamma. The proof then uses Lemma 8.2 to get a static algorithm with running time r^{Psi_K(s)+o(1)}. The inequality Psi_K(s) < 2 is required to contradict OVC. The proof states that for every fixed K, Psi_K(s) < 2. This is true if s < 2, which holds because gamma > 0. However, the lemma also requires that the initialization time is m^{K+o(1)}. Here the initialization time is n^K p(...), which is n^{K+o(1)}. So K is the exponent of n in initialization. The proof then chooses m = r^{Theta(1)} to balance terms. This is valid. The corollary is correctly argued, but the presentation could be clearer about the relationship between K, gamma, and the exponents.","section":"Section 8.3, Corollary 8.3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The lemma constructs an exact rational alpha-centerpoint with alpha^{-1} = poly(D, log(1/phi)). The proof uses a linear program with r blocks of s samples each. The sample sizes are s = ceil(C (D+1)^2 L) and r = ceil(C (D+1) s L), where L = log(2(D+2)/phi). The VC uniform convergence bound requires that rs >= C_0 s^2 ((D+1) log(s+1) + log(2/phi)). The authors state that their choices meet this inequality. It would be helpful to provide a brief verification or cite a standard reference. The current proof is sketchy.","section":"Appendix A, Lemma A.1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The finite splitter family is taken from Wei [Wei19, Proposition 11]. The authors state that the number of finite seed choices is exp(O(s log B_0)). This is correct, but the exact dependence on the error parameter epsilon is not given. The error is O(b^{-1/2}), and b = Theta(log^{2/3} m). So the number of splitters is exp(O( (B_0/b) log B_0 )) = exp(O( (L^{2zeta} ell^{1/3}) log(L^{2zeta} ell) )) = m^{o(1)}. This is consistent with the claim that the splitter family size is m^{o(1)}. The authors should make this explicit.","section":"Appendix B.1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof of Theorem D.1 chooses all margins as functions of n, with L = max{2, log(2n)} and zeta = 1/100. The moderate block dimension is B_mod = Theta_c(L^{2zeta} ell), where ell = log m. For m >= exp(sqrt(L)), ell >= sqrt(L), so B_mod = Theta_c(L^{2zeta} sqrt(L)) = Theta_c(L^{0.5 + 2zeta}) = Theta_c(L^{0.7}). This is subpolynomial in n. The splitter dimension b = Theta(ell^{2/3}) = Theta(L^{1/3}). The number of splitters is exp(O(s log B_mod)) = exp(O( (B_mod/b) log B_mod )) = exp(O( L^{0.7 - 1/3} log L )) = exp(O( L^{0.366...} log L )) = n^{o(1)}. This is consistent. The proof is sound but dense. A brief summary of the parameter scaling would improve readability.","section":"Appendix D","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The paper uses the notation poly_c(d, L) to denote a polynomial in d and L whose degree and coefficients may depend on c. This is convenient, but it would be helpful to state explicitly that the polynomial degree is fixed for each c and does not grow with n. The paper does this in Section 3 ('Its coefficients and degree may depend on the fixed approximation and space parameters, but not on the input'). This is clear.","section":"General","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"major_revision"},"author_rebuttal":null,"desk_editor":null,"pith_extraction":{"msc":["68W20","68W25","68U05","68P20"],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"This paper claims to achieve fully dynamic high-dimensional diameter approximation below √2 with an update exponent that tends to zero at √2, improving Indyk's classic bound.","keywords":["dynamic diameter","farthest-neighbor search","high-dimensional geometry","centerpoint","adaptive adversary","locality-sensitive filtering","function inversion","approximation algorithms"],"falsifier":"Implement the algorithm for a specific c, say c=√(3/2), on a sequence of n points in dimension d=O(log n) with n=1000, and test whether the reported diameter pair is indeed within factor c of the true diameter after a sequence of adaptive deletions designed to expose all filter randomness. If the algorithm ever returns a pair whose distance is below the true diameter divided by c, the central claim is falsified.","tokens_in":53898,"feed_emoji":"📐","tokens_out":1483,"duration_ms":15274,"temperature":0.7,"pith_summary":"The paper presents fully dynamic data structures for maintaining a factor-c approximate diameter pair in high-dimensional Euclidean space under arbitrary point insertions and deletions, with worst-case update time and space that improve on previous work. For every fixed c between 1 and √2, the update exponent is 2/c² - 1, which tends to zero as c approaches √2. A separate structure achieves approximation exactly √2 with polylogarithmic update time. All guarantees hold against adaptive adversaries that see previous random choices. The key geometric idea augments a centerpoint with a second-moment coordinate to preserve a variance identity that survives deletions, reducing remaining searches to a common angular separation problem.","feed_headline":"Dynamic diameter below √2 with update exponent tending to zero","feed_subtitle":"A lifted centerpoint preserves variance, enabling faster updates and robustness to exposed randomness.","key_machinery":"The central object is a lifted centerpoint: for a fixed set of points, each point is replaced by its paraboloid lift (p, ||p||²) in one higher dimension. A point z = (o, s) of high halfspace depth in this lifted set gives a center o and a variance V = s - ||o||² ≥ 0. This yields two geometric guarantees: (1) a constant fraction of birth points lie in the core ball B(o, √V), and (2) for every query q, a constant fraction of birth points satisfy ||p - q||² ≥ V + ||q - o||², i.e., they witness a distance lower bound. These guarantees survive deletions and hold simultaneously for all queries.","core_discovery":"The paper's central discovery is that augmenting a centerpoint with a squared-norm coordinate before choosing the representative preserves a variance term that is absent from the original-space argument. This gives a stronger distance witness than the original-space representative and makes the remaining searches instances of one common angular gap. The resulting variance identity supplies many distance witnesses that survive deletions, and reduces the remaining searches to a common angular separation problem. This yields a fully dynamic factor-c diameter pair with worst-case update time $n^{{2/c²-1}}$ poly(d, log n) and space $n^{{2/c²}}$ poly(d, log n), improving Indyk's update exponent from 1/c² to 2/c²-1 and the space exponent from 1+1/c² to 2/c².","pith_inferences":["The approach may extend to other high-dimensional proximity problems, such as dynamic closest pair or dynamic minimum enclosing ball, by using similar variance certificates.","The reliance on approximate centerpoint constructions with polynomial dependence on dimension means the practical performance may be limited to moderate dimensions, despite the theoretical guarantees.","The paper's lower bound arguments suggest that achieving update time n^{1-γ} for (1+ε)-approximation would violate the randomized Orthogonal Vectors Conjecture, indicating a barrier for near-exact approximation in dynamic settings."],"forward_implications":["If correct, this gives the first fully dynamic diameter structure below √2 with an update exponent that tends to zero at √2, answering an open question.","The improvement over Indyk's algorithm is quantitative: at c=√(3/2), the update exponent drops from 2/3 to 1/3.","The structure handles adaptive adversaries that see previous random choices, making it suitable for use as a subroutine in other algorithms.","The same geometry gives improved static diameter algorithms and farthest-neighbor search structures, including for Hamming distance.","A separate construction achieves approximation exactly √2 with polylogarithmic update time, polynomial in dimension and log n."],"supporting_citations":[{"why":"Supplies the baseline dynamic diameter algorithm with update exponent 1/c² and space exponent 1+1/c² that this work improves upon.","marker":"[Ind03]"},{"why":"Introduces the centerpoint method for adaptive dynamic diameter and supplies the robust dynamic model used here.","marker":"[BGG+25]"},{"why":"Provides the approximate centerpoint construction used to compute the lifted centerpoint with polynomial time and depth guarantee.","marker":"[HPJ19]"},{"why":"Supplies the asymmetric Gaussian filtering framework used for angular search with explicit filter lists.","marker":"[Chr17]"},{"why":"Provides the finite splitting families used in the certified (zero-error) angular search construction.","marker":"[Wei19]"},{"why":"Supplies the bounded-fiber function inversion technique used for the implicit representation of point-filter incidences.","marker":"[BBM26]"},{"why":"Provides the phase organization and dynamic inversion schedule used for the implicit search structure.","marker":"[KK26]"},{"why":"Supplies the INDEX lower bound construction adapted to show linear space is necessary below √2.","marker":"[AS15]"},{"why":"Provides the previous best static Hamming diameter and farthest-neighbor bounds that this work improves on binary inputs.","marker":"[AJZ26]"}],"fun_headline_variants":[],"cache_read_input_tokens":0,"weakest_assumption_plain":"The fully adaptive guarantee (exposed randomness still yields correctness) rests on the assumption that a single success event holds simultaneously for every query direction and every subset of a birth pool, requiring a finite direction-net cover and a union bound over the net and birth targets. If this amplification fails by a constant, the worst-case update bound against an adversary that sees all previous random choices collapses.","fun_headline_variants_meta":{"raw":{"variants":[]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":0.000496,"raw_usage":{"cost":0.0004956042,"is_byok":false,"cost_details":{"upstream_inference_cost":0.0004956042,"upstream_inference_prompt_cost":8.90162e-05,"upstream_inference_completions_cost":0.000406588},"total_tokens":3417,"prompt_tokens":1183,"completion_tokens":2234,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":256,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":0}},"tokens_in":1183,"tokens_out":2234,"cost_source":"openrouter_usage","duration_ms":13640,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":0,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-13T07:28:44.995521+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"Implement the algorithm for a specific c, say c=√(3/2), on a sequence of n points in dimension d=O(log n) with n=1000, and test whether the reported diameter pair is indeed within factor c of the true diameter after a sequence of adaptive deletions designed to expose all filter randomness. If the algorithm ever returns a pair whose distance is below the true diameter divided by c, the central claim is falsified.","supporting_citations":[],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}