Pith.

Data Structures and Algorithms · arXiv:2611.17050 v1 · submitted 12 Nov 2026 · 39 references

Finding the Farthest in High Dimensions: Dynamic Diameter and Farthest-Neighbor Search

Mohammad Hajiaghayi, Morteza Monemizadeh

The paper says

“We give faster algorithms for diameter and farthest-neighbor search in high-dimensional Euclidean space.”

more of the abstract

For every fixed 1 < c < √2, we maintain an actual factor-c diameter pair under arbitrary point insertions and deletions, with worst-case update time $n^{2/c^2-1}\poly(d,\log n)$ and space $n^{2/c^2}\poly(d,\log n)$, suppressing logarithmic dependence on the execution length and failure probability. Here n bounds the number of active points. The update exponent improves Indyk's algorithm i̧teindyk (SODA'03) bound from 1/c2 to 2/c2−1, while the space exponent improves from 1 + 1/c2 to 2/c2. At c = √(3/2), the update exponent decreases from 2/3 to 1/3. A separate construction achieves approximation exactly √2 with update time polynomial in d and logn. All these guarantees hold against adaptive updates, even when every previous random choice is exposed. We also improve the time–space tradeoff near linear space. This construction has an always-correct variant with expected amortized update bounds and requires no advance bound on the number of updates. The dynamic structures store a current answer, so reporting its two point identifiers takes constant time. The geometric method also gives static diameter algorithms and a farthest-neighbor structure for a fixed set that answers arbitrary adaptive queries. At approximation √2−ε, the diameter time is n1 + O(ε), and the query time is nO(ε) + o(1) with near-linear preprocessing and space, up to polynomial input-parameter factors. On binary points, this improves the nO(√θ) overhead of the algorithm that Andoni, Jiang, and Zharkov i̧teajz2026 (STOC'26) for Hamming approximation 2−θ to nO(θ) + o(1).

from the abstract

Pith says

Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

Holds up, with conditions.

4 major objections · 10 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the 39 references say.

The paper says, at Section 6.1, Lemma 6.3 and the paragraph 'One event for all adaptive queries'

The review did not quote this passage.

Pith says: Objection 1 of 4 · major

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.

more of objection 1

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.

The paper says, at Section 6.2, Proposition 6.4 and Appendix B

The review did not quote this passage.

Pith says: Objection 2 of 4 · major

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.

more of objection 2

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.

The paper says, at Section 7.3, 'One failure budget for the whole execution'

The review did not quote this passage.

Pith says: Objection 3 of 4 · major

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.

more of objection 3

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.

The paper says, at Section 9.2, Lemma 9.2 and the implicit tradeoff

The review did not quote this passage.

Pith says: Objection 4 of 4 · major

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.

more of objection 4

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.

10 minor objections

The paper says, at Abstract and Section 1

Pith says: minor objection 1 of 10

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.

The paper says, at Section 2.1, Figure 3

Pith says: minor objection 2 of 10

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.

show 8 more

The paper says, at Section 5.2, Lemma 5.3

Pith says: minor objection 3 of 10

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.

more of objection 3

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.

The paper says, at Section 6.1, Lemma 6.3

Pith says: minor objection 4 of 10

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}.

more of objection 4

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.

The paper says, at Section 7.1, Lemma 7.1

Pith says: minor objection 5 of 10

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.'

more of objection 5

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.

The paper says, at Section 8.3, Corollary 8.3

Pith says: minor objection 6 of 10

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.

more of objection 6

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.

The paper says, at Appendix A, Lemma A.1

Pith says: minor objection 7 of 10

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).

more of objection 7

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.

The paper says, at Appendix B.1

Pith says: minor objection 8 of 10

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.

more of objection 8

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.

The paper says, at Appendix D

Pith says: minor objection 9 of 10

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}).

more of objection 9

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.

The paper says, at General

Pith says: minor objection 10 of 10

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.

What would settle it

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.

from the skeptic's reading

How the review went

3 readings by deepseek-v4-flash · 13 Nov 2026

  1. Reader holds up, with conditions confidence moderate
  2. Skeptic agrees 2 min 39 s · 52,593 tokens read, 23,037 written
  3. Referee major revision: 4 major objections, 10 minor 23 s · 52,898 tokens read, 3,511 written

Not run on this paper: the editor, the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The strongest objection

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.

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.

The referee's report

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.

Pith's reading of the paper (a machine's summary, not the authors')

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.

What carries the argument. 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 claim. 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².

The premise it rests on. 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.

If the paper is right (Pith's inferences, not the authors')

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.

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.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

We give faster algorithms for diameter and farthest-neighbor search in high-dimensional Euclidean space. For every fixed 1 < c < √2, we maintain an actual factor-c diameter pair under arbitrary point insertions and deletions, with worst-case update time $n^{2/c^2-1}\poly(d,\log n)$ and space $n^{2/c^2}\poly(d,\log n)$, suppressing logarithmic dependence on the execution length and failure probability. Here n bounds the number of active points. The update exponent improves Indyk's algorithm i̧teindyk (SODA'03) bound from 1/c2 to 2/c2−1, while the space exponent improves from 1 + 1/c2 to 2/c2. At c = √(3/2), the update exponent decreases from 2/3 to 1/3. A separate construction achieves approximation exactly √2 with update time polynomial in d and logn. All these guarantees hold against adaptive updates, even when every previous random choice is exposed. We also improve the time–space tradeoff near linear space. This construction has an always-correct variant with expected amortized update bounds and requires no advance bound on the number of updates. The dynamic structures store a current answer, so reporting its two point identifiers takes constant time. The geometric method also gives static diameter algorithms and a farthest-neighbor structure for a fixed set that answers arbitrary adaptive queries. At approximation √2−ε, the diameter time is n1 + O(ε), and the query time is nO(ε) + o(1) with near-linear preprocessing and space, up to polynomial input-parameter factors. On binary points, this improves the nO(√θ) overhead of the algorithm that Andoni, Jiang, and Zharkov i̧teajz2026 (STOC'26) for Hamming approximation 2−θ to nO(θ) + o(1).

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-11-13

The authors' main claim, as the classifier picked it out 1.00

“We give faster algorithms for diameter and farthest-neighbor search in high-dimensional Euclidean space.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.05 · states limitation 0.42 · human participants 0.01 · controlled comparison 0.09 · randomized assignment 0.04 · states quantitative result 0.98 · compares with prior results 0.98 · mentions code or data availability 0.02

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
We give faster algorithms for diameter and farthest-neighbor search in high-dimensional Euclidean space. contribution 1.00 0.95 0.75 asserted 1.00
For every fixed $1<c<\sqrt2$, we maintain an actual factor-$c$ diameter pair under arbitrary point insertions and deletions, with worst-case update time $n^{2/c^2-1}\poly(d,\log n)$ and space $n^{2/c^2}\poly(d,\log n)$, suppressing logarithmic dependence on the execution length and failure probability. contribution 0.64 0.95 0.37 asserted 1.00
Here $n$ bounds the number of active points. background 0.70 0.16 0.03 asserted 0.81
The update exponent improves Indyk's algorithm~\cite{indyk} (SODA'03) bound from $1/c^2$ to $2/c^2-1$, while the space exponent improves from $1+1/c^2$ to $2/c^2$. result 0.46 0.73 0.15 asserted 1.00
At $c=\sqrt{3/2}$, the update exponent decreases from $2/3$ to $1/3$. result 0.95 0.82 0.07 asserted 1.00
A separate construction achieves approximation exactly $\sqrt2$ with update time polynomial in $d$ and $\log n$. contribution 0.54 0.90 0.07 asserted 1.00
All these guarantees hold against adaptive updates, even when every previous random choice is exposed. result 0.68 0.88 0.05 asserted 1.00
We also improve the time--space tradeoff near linear space. contribution 0.80 0.91 0.07 asserted 1.00
This construction has an always-correct variant with expected amortized update bounds and requires no advance bound on the number of updates. contribution 0.72 0.90 0.05 asserted 1.00
The dynamic structures store a current answer, so reporting its two point identifiers takes constant time. result 0.66 0.91 0.04 asserted 1.00
The geometric method also gives static diameter algorithms and a farthest-neighbor structure for a fixed set that answers arbitrary adaptive queries. contribution 0.90 0.94 0.08 asserted 1.00
At approximation $\sqrt2-\varepsilon$, the diameter time is $n^{1+O(\varepsilon)}$, and the query time is $n^{O(\varepsilon)+o(1)}$ with near-linear preprocessing and space, up to polynomial input-parameter factors. result 0.87 0.91 0.10 asserted 1.00
On binary points, this improves the $n^{O(\sqrt\theta)}$ overhead of the algorithm that Andoni, Jiang, and Zharkov~\cite{ajz2026} (STOC'26) for Hamming approximation $2-\theta$ to $n^{O(\theta)+o(1)}$. result 0.74 0.79 0.06 asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.86 · evidence from proof or derivation 1.00

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-13: 1 request, 9,793 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

Figures (4)
Figure 1 of the paper
Figure 1. Update exponents as a function of the approximation factor. The red curve improves
Figure 2 of the paper
Figure 2. The time–space tradeoff at c = p 9/5. Space is n 1+σ up to polynomial factors. The implicit construction replaces the initial part of the explicit curve by its tangent at uc ≈ 0.0205, improving the update exponent near linear space. Its running time has an additional vanishing o(1) term; the space exponent stays 1 + σ. Expected amortized time bounds the expected total work over every fixed finite prefix of an adaptive execution starting from the empty set. It includes construction, unsuccessful attempts, and rebuilding. The space bound includes all simultaneously live structures and
Figure 3 of the paper
Figure 3. Two examples of the certificate. In (a), the nine points
Figure 4 of the paper
Figure 4. The cores partition the active set together with the terminal set. A diametral pair is

Figures are the authors', reproduced from the paper.

References (39)
  1. [1] Piotr Indyk , title=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2003 , url= on Pith
  2. [2] Timothy M. Chan and Vinayak Pathak , title=. Computational Geometry , volume=. 2014 , doi= on Pith
  3. [3] Pankaj K. Agarwal and R. Sharathkumar , title=. Algorithmica , volume=. 2015 , doi= on Pith
  4. [4] Kiarash Banihashem and Jeff Giliberti and Samira Goudarzi and MohammadTaghi Hajiaghayi and Peyman Jabbarzade and Morteza Monemizadeh , title=. Advances in Neural Information Processing Systems (NeurIPS) , volume=. 2025 , doi= on Pith
  5. [5] Kiarash Banihashem and Jeff Giliberti and Prashant Gokhale and Samira Goudarzi and Mohammadtaghi Hajiaghayi and Yuhao Liu and Morteza Monemizadeh and Sandeep Silwal , title=. Proceedings of the 43rd International Conference on Machine Learning , series=. 2026 , url= on Pith
  6. [6] Aviad Rubinstein , title=. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , year= on Pith
  7. [7] Lijie Chen and Ryan Williams , title=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , year= on Pith
  8. [8] Josh Alman and Timothy M. Chan and Ryan Williams , title=. 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS) , year= on Pith
  9. [9] Josh Alman and Timothy M. Chan and Ryan Williams , title=. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2020 , doi= on Pith
  10. [10] Thomas D. Ahle and Michael Kapralov and Jakob B. T. Knudsen and Rasmus Pagh and Ameya Velingker and David P. Woodruff and Amir Zandieh , title=. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) , year= on Pith
  11. [11] Karthik Gajulapalli and Alexander Golovnev and Samuel King and Sidhant Saraogi , title=. 2026 , note= on Pith
  12. [12] Tobias Christiani , title=. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2017 , doi= on Pith
  13. [13] David Eppstein , title=. Discrete & Computational Geometry , volume=. 1995 , doi= on Pith
  14. [14] Sariel Har-Peled and Mitchell Jones , title=. 35th International Symposium on Computational Geometry (SoCG) , series=. 2019 , doi= on Pith
  15. [15] Ashish Goel and Piotr Indyk and Kasturi Varadarajan , title=. Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2001 , url= on Pith
  16. [16] Alexandr Andoni and Shunhua Jiang and Stepan Zharkov , title=. Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC) , pages=. 2026 , doi= on Pith
  17. [17] David Haussler and Emo Welzl , title=. Discrete & Computational Geometry , volume=. 1987 , doi= on Pith
  18. [18] Vladimir N. Vapnik and Alexey Ya. Chervonenkis , title=. Theory of Probability & Its Applications , volume=. 1971 , doi= on Pith
  19. [19] Martin Gr. Geometric Algorithms and Combinatorial Optimization , publisher= on Pith
  20. [20] Kunal Dutta and Karol Pisula , title=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , doi= on Pith
show 19 more
  1. [21] Alexandr Andoni and Ilya Razenshteyn , title=. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC) , pages=. 2015 , doi= on Pith
  2. [22] Alexandr Andoni and Thijs Laarhoven and Ilya Razenshteyn and Erik Waingarten , title=. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2017 , doi= on Pith
  3. [23] Jon Louis Bentley and James B. Saxe , title=. Journal of Algorithms , volume=. 1980 , doi= on Pith
  4. [24] Timothy M. Chan , title=. 32nd International Symposium on Computational Geometry (SoCG) , series=. 2016 , doi= on Pith
  5. [25] Ashwin Padaki and Krish Singal and Erik Waingarten , title=. 2026 , note= on Pith
  6. [26] Sanjeev Khanna and Ashwin Padaki and Krish Singal and Erik Waingarten , title=. 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) , year= on Pith
  7. [27] Magn. Streaming Diameter of High-Dimensional Points , booktitle=. 2025 , doi= on Pith
  8. [28] Lotte Blank and Sergio Cabello and Mohammad Taghi Hajiaghayi and Robert Krauthgamer and Sepideh Mahabadi and Andr. The Expiration Streaming Model: Diameter,. 53rd International Colloquium on Automata, Languages, and Programming (ICALP) , series=. 2026 , doi= on Pith
  9. [29] Elie Abboud and Noga Ron-Zewi , title=. 51st International Colloquium on Automata, Languages, and Programming (ICALP) , series=. 2024 , doi= on Pith
  10. [30] Alexandr Andoni and Ilya Razenshteyn , title=. 32nd International Symposium on Computational Geometry (SoCG) , series=. 2016 , doi= on Pith
  11. [31] Sariel Har-Peled and Timothy Zhou , title=. 29th Annual European Symposium on Algorithms (ESA) , series=. 2021 , doi= on Pith
  12. [32] Gabriel Bathie and Guillaume Lagarde , title=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=. 2025 , doi= on Pith
  13. [33] Alexander Wei , title=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2019 , doi= on Pith
  14. [34] Cheng Jiang and Yinchen Liu and Huacheng Yu , title=. 2026 , eprint= on Pith
  15. [35] Samuel McCauley , title=. 32nd Annual European Symposium on Algorithms (ESA) , series=. 2024 , doi=. 2407.02468 , archivePrefix= on PithPith's reviewarXiv
  16. [36] John Kuszmaul and William Kuszmaul , title=. 2026 , eprint= on Pith
  17. [37] Jackson Bibbens and Levi Borevitz and Samuel McCauley , title=. Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC) , pages=. 2026 , doi=. 2604.01307 , archivePrefix= on PitharXiv
  18. [38] Boris Aronov and Jean Cardinal and Justin Dallant and John Iacono , title=. 2024 Symposium on Simplicity in Algorithms (SOSA) , pages=. 2024 , doi=. 2311.12471 , archivePrefix= on PithPith's reviewarXiv
  19. [39] Mathieu Vannimmen , title=. 2026 , eprint= on Pith

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment