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
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
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
- Reader holds up, with conditions
- Skeptic agrees
- Referee major revision: 4 major objections, 10 minor
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
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.
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.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| 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)
Figures are the authors', reproduced from the paper.
References (39)
- [1] Piotr Indyk , title=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2003 , url= on Pith
- [2] Timothy M. Chan and Vinayak Pathak , title=. Computational Geometry , volume=. 2014 , doi= on Pith
- [3] Pankaj K. Agarwal and R. Sharathkumar , title=. Algorithmica , volume=. 2015 , doi= on Pith
- [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] 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] Aviad Rubinstein , title=. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , year= on Pith
- [7] Lijie Chen and Ryan Williams , title=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , year= on Pith
- [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] 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] 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] Karthik Gajulapalli and Alexander Golovnev and Samuel King and Sidhant Saraogi , title=. 2026 , note= on Pith
- [12] Tobias Christiani , title=. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2017 , doi= on Pith
- [13] David Eppstein , title=. Discrete & Computational Geometry , volume=. 1995 , doi= on Pith
- [14] Sariel Har-Peled and Mitchell Jones , title=. 35th International Symposium on Computational Geometry (SoCG) , series=. 2019 , doi= on Pith
- [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] 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] David Haussler and Emo Welzl , title=. Discrete & Computational Geometry , volume=. 1987 , doi= on Pith
- [18] Vladimir N. Vapnik and Alexey Ya. Chervonenkis , title=. Theory of Probability & Its Applications , volume=. 1971 , doi= on Pith
- [19] Martin Gr. Geometric Algorithms and Combinatorial Optimization , publisher= on Pith
- [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
- [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
- [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
- [23] Jon Louis Bentley and James B. Saxe , title=. Journal of Algorithms , volume=. 1980 , doi= on Pith
- [24] Timothy M. Chan , title=. 32nd International Symposium on Computational Geometry (SoCG) , series=. 2016 , doi= on Pith
- [25] Ashwin Padaki and Krish Singal and Erik Waingarten , title=. 2026 , note= on Pith
- [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
- [27] Magn. Streaming Diameter of High-Dimensional Points , booktitle=. 2025 , doi= on Pith
- [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
- [29] Elie Abboud and Noga Ron-Zewi , title=. 51st International Colloquium on Automata, Languages, and Programming (ICALP) , series=. 2024 , doi= on Pith
- [30] Alexandr Andoni and Ilya Razenshteyn , title=. 32nd International Symposium on Computational Geometry (SoCG) , series=. 2016 , doi= on Pith
- [31] Sariel Har-Peled and Timothy Zhou , title=. 29th Annual European Symposium on Algorithms (ESA) , series=. 2021 , doi= on Pith
- [32] Gabriel Bathie and Guillaume Lagarde , title=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=. 2025 , doi= on Pith
- [33] Alexander Wei , title=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2019 , doi= on Pith
- [34] Cheng Jiang and Yinchen Liu and Huacheng Yu , title=. 2026 , eprint= on Pith
- [35] Samuel McCauley , title=. 32nd Annual European Symposium on Algorithms (ESA) , series=. 2024 , doi=. 2407.02468 , archivePrefix= on PithPith's reviewarXiv
- [36] John Kuszmaul and William Kuszmaul , title=. 2026 , eprint= on Pith
- [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
- [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
- [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.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment