{"id":"eca95a89-8d31-4161-aa15-920c2c7d5df1","arxiv_id":"2411.14336","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"For random nearest neighbor trees, the root can be found among a confidence set of size roughly log(1/epsilon) divided by log log(1/epsilon) in one dimension.","lead":"This paper studies how to find the first vertex in a randomly growing nearest neighbor tree on a torus, and it proves near-tight bounds on the size of the candidate set needed in one dimension. It introduces embedded, metric, and graph versions of root finding, showing that geometric information makes the root substantially easier to locate than in classic random tree models.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The d≥2 upper bound (Theorem 1.2, Lemma 5.2) depends on an unproved structural assertion in §5.1: the earlier endpoint of an early long edge is within graph distance 7 log k of the root in the uncovered subgraph. No proof is given, and Algorithm 4 expands only in that subgraph.","rationale":"Reader's verdict: agree. This is exactly the weakest assumption the reader flagged, and it is the most load-bearing of the two concerns. The d=1 direction error in Section 3.3 is real but superficial: replacing '≥' with '≤' in claim (ii) makes the intended lower-bound argument work, and the final inequality (8) is the correct necessary condition. By contrast, the d≥2 structural claim is not a sign slip; it is a mathematically nontrivial high-probability statement about uncovered-subgraph connectivity, and Theorem 1.2's proof simply assumes it. Because Algorithm 4's expansion is restricted to U_n, a long edge whose root-to-edge path in U_n is much longer than k (or blocked by covered vertices) would cause the confidence set to miss the root; the paper provides no argument excluding this. The confidence-set size bound (16) and the runtime analysis also rely on the bounded degree of U_n, so the missing lemma cannot be bypassed by expanding in the full tree. Thus the d≥2 upper bound is not proven as submitted, and the reader's CONDITIONAL verdict should stand pending this proof. The paper has independent merit: the d=1 algorithm and lower bound are essentially sound modulo the repairable inequality, and Lemma 5.1 is a useful structural result.","tokens_in":22606,"tokens_out":31600,"duration_ms":276269,"concrete_test":"Independently re-derive the §5.1 structural claim: from Definition 5.1 and Lemma 5.1, prove that the earlier endpoint of the first long edge among the first k steps is within graph distance 7 log k of the root in U_n with probability at least 1−ε, for k and ℓ as in (13). If the derivation cannot be completed without an extra unstated hypothesis (e.g., a uniform bound on the number of consecutive covered vertices on the root-to-edge path), that hypothesis must be isolated and proved; until then, Lemma 5.2 does not establish the d≥2 upper bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most serious gap is in the proof of the d ≥ 2 upper bound, Theorem 1.2 via Lemma 5.2. Section 5.1 lists as a 'crucial structural component' the assertion that, with high probability, if one of the first k edges is long, the earlier vertex adjacent to that edge is at graph distance at most 7 log k from the root in the induced subgraph of uncovered vertices U_n. No lemma, proof, or citation is supplied before Lemma 5.2 uses the assertion. The correctness step of Lemma 5.2 says 'if any of the first k edges are long, then the algorithm successfully includes the root'; but Algorithm 4 builds H(ε,n) by expanding only through U_n (which has bounded degree by Lemma 5.1), so the trivial full-tree distance bound from time indices — at most k — does not imply that the root lies within distance k of the edge in U_n. The confidence-set bound (16) and the runtime bound also count only uncovered vertices. Without the missing O(log k) structural bound, nothing in the proof rules out the possibility that the root-to-edge path in U_n is long or absent, in which case the returned confidence set may miss the root. The paper itself flagging this as a structural component makes it a missing-support issue rather than a dispute with existing results.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies root finding in random nearest neighbor trees on the d-dimensional torus, where the algorithm receives the unlabeled embedded tree (or metric information) and must return a confidence set containing the root with probability at least 1−ε. The main results are: for d=1, an O(n^2 + log^2(1/ε))-time algorithm with confidence set size Θ(log(1/ε)/log log(1/ε)), matching an information-theoretic lower bound; for d≥2, an algorithm with subpolynomial confidence set size and a polylogarithmic lower bound. The algorithms are based on long edges and the induced subgraph of uncovered vertices, and the lower bounds use maximum-likelihood comparisons on specially constructed path-like families.","tokens_in":22852,"tokens_out":24143,"duration_ms":198569,"significance":"If the results are correct, they establish that geometric information dramatically reduces the root-finding difficulty compared to uniform and preferential attachment trees, where confidence sets must be subpolynomial in 1/ε. The paper also introduces a clean framework (embedded, metric, and graph root finding) and provides explicit algorithms with runtime guarantees as well as information-theoretic lower bounds. However, the significance is conditional on closing the gaps below, particularly the unproved structural assertion underlying the d≥2 upper bound.","major_comments":[{"comment":"The correctness of Algorithm 4 in Lemma 5.2 depends on the claim, listed in the introduction to Section 5.1, that with high probability the earlier endpoint of an early long edge is within graph distance 7 log k of the root in the induced subgraph of uncovered vertices U_n. This claim is asserted without a proof, a lemma, or a citation, and the subsequent proof of Lemma 5.2 uses it implicitly when it states that if any of the first k edges are long then the algorithm includes the root. Since Algorithm 4 expands only through U_n, the trivial full-tree distance bound of at most k from time indices does not imply that the root is near the edge in U_n. Without a proof of this O(log k) structural bound, the upper bound of Theorem 1.2 is not established. The authors should provide a complete proof or reference for this assertion, and also prove that the root is always uncovered (or otherwise handle the covered case).","section":"§5.1, Lemma 5.2"},{"comment":"The lower-bound proof for d=1 contains an inequality-direction error. The family F of trees has probability 2(K(ε)+5)^{-(K(ε)+1)}. The text states that this is at least ε when K(ε) satisfies (K(ε)+1)log(K(ε)+5) ≥ log(2/ε), but the reverse inequality is required: one needs (K(ε)+1)log(K(ε)+5) ≤ log(2/ε) for the probability to be at least ε. As written, claim (ii) is false, and the proof does not show that the constructed family is ε-likely. Although the final lower bound in Eq. (8) has the correct direction if the argument is repaired, the current proof is not valid.","section":"§3.3, claim (ii)"}],"minor_comments":[{"comment":"The line 'to argue that P{1 ̸∈ H(ε, n)} ≥ 1 − ε' should read 'P{1 ∈ H(ε, n)} ≥ 1 − ε' or 'P{1 ̸∈ H(ε, n)} ≤ ε'.","section":"§3.2, Lemma 3.3 proof"},{"comment":"The phrase 'expected size X_{K+1}' should be 'expected time' or 'E[X_{K+1}]', since X_{K+1} is a time index, not a size.","section":"§3.1, Lemma 3.1"},{"comment":"The treatment of constants is a bit loose: after absorbing factors into a universal constant, the statement should clarify that the constant may depend on the fixed dimension d and does not claim uniformity in d.","section":"§5.2, Eq. (14) and Eq. (16)"},{"comment":"The phrase 'all edges added before then are long' is misleading; the claim proves a lower bound L on the projected edge lengths, not that the edges are long in the ε-dependent sense of the algorithm. Please rephrase.","section":"§4.1, Claim 1"},{"comment":"The direction-assignment procedure for covered vertices is described only informally; a precise iterative or recursive description would help the reader verify termination and consistency of the cover marking.","section":"§5.2, Algorithm 4, Step 1"},{"comment":"The sentence 'Therefore, the runtime of Step 2 is bounded above by log^2(1/ε)' should be written as O(log^2(1/ε)) and should clarify why the n-dependence of Step 2 is absorbed.","section":"§3.2, Lemma 3.3 proof"}],"recommendation":"major_revision","confidential_remarks":"The main risk to the paper is the unproved structural assertion in Section 5.1; if it cannot be proved, the upper bound of Theorem 1.2 should be withdrawn or reformulated. The inequality direction in Section 3.3 is likely a typo, but it must be corrected for the lower-bound proof to be valid. The d≥2 lower-bound proof via the contrapositive of Eq. (18) is logically sound; I found no issue there. The d=1 upper bound and the thin-strip result appear well argued aside from presentation issues."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know two things about arXiv:2411.14336. First, it answers a real open question from Lichev and Mitsche by giving the first root-finding bounds for random nearest neighbor trees, and in d=1 the bounds are tight: Θ(log(1/ε)/log log(1/ε)). Second, the paper as submitted has a genuine gap in the d≥2 upper bound and a smaller sign error in the 1D lower bound; both are fixable, but the d≥2 gap needs real work.\n\nWhat's new and good: the three problem formulations (embedded, metric, graph) are natural and will likely stick. The metric algorithm that returns endpoints of long edges is simple and gives O(1/ε) size, with a nice early-arrival guarantee. The 1D upper bound uses the uncovered-vertices path structure cleverly, and the lower bound via a family of path-shaped trees is a clean adaptation of Bubeck–Devroye–Lugosi. The writing is clear, and the paper is honest about what remains open.\n\nSoft spots:\n\n1. Section 5 (d≥2). Lemma 5.2's correctness step relies on the claim that, when an early edge is long, the earlier endpoint is within graph distance 7 log k of the root in the induced subgraph of uncovered vertices. This is announced as a “crucial structural component” in §5.1, but no proof or reference is given. Since Algorithm 4 expands only through the uncovered subgraph U_n, the trivial time-index bound does not suffice, and without the missing lemma the confidence set could in principle miss the root. This is load-bearing, not a nit. The assertion may be true, but it needs proof.\n\n2. Section 3.3. The comparison of the family probability 2(K+5)^{-(K+1)} to ε goes the wrong direction: for the family to have probability at least ε you need (K+1)log(K+5) ≤ log(2/ε), not ≥. The final lower bound statement is correct, and the fix is straightforward, but as written it is a sign error.\n\n3. Minor: the statement of the d≥2 lower bound in Theorem 1.2 has an awkward exponent |H|^{(d-1)/d}; the lemma in §5.3 is cleaner and likely the intended form.\n\nBottom line: the 1D results look right modulo the sign fix, and the metric algorithm is solid. The d≥2 upper bound is the main concern—I would want to see the missing structural lemma proved before trusting Theorem 1.2. This is absolutely worth serious refereeing: it opens a new direction and the core ideas are good. I would recommend conditional acceptance after the authors fill the gap; a desk rejection would be wrong.\n\nFor a reading group, this is a good paper to discuss—both for the clever 1D construction and as an example of a missing-load-bearing-lemma situation.","headline":"Genuinely new root-finding results for geometric random trees, with a tight 1D story; the d≥2 upper bound currently rests on an unproved structural claim, so the proof needs revision before the result is complete.","tokens_in":23438,"tokens_out":4081,"would_cite":true,"duration_ms":34696,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60D05","05C80","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"For a random nearest neighbor tree on the 1-D torus, an efficient algorithm returns a confidence set of size $\\Theta(\\log(1/\\varepsilon)/\\log\\log(1/\\varepsilon))$ containing the root with probability $1-\\varepsilon$, and matching lower…","keywords":["root finding","network archaeology","random nearest neighbor tree","geometric random graphs","confidence sets","uncovered vertices","long edges","random recursive trees"],"falsifier":"Simulate 2-NN trees on the unit torus for large $n$ and small $\\varepsilon$; among the first $k = \\gamma \\log(1/\\varepsilon)$ edges, find the first edge of length at least $\\ell = (C(d)\\,\\gamma\\, e^{1/\\gamma} \\log(1/\\varepsilon))^{-1/d}$ and measure the graph distance in the uncovered subgraph from the earlier endpoint of that edge to vertex 1. If this distance exceeds $7\\log k$ with non-negligible probability for some $\\varepsilon$, the correctness claim behind Lemma 5.2 fails.","tokens_in":22310,"feed_emoji":"🌳","tokens_out":11379,"duration_ms":90060,"temperature":0.7,"pith_summary":"This paper asks whether the geometry of a randomly grown tree reveals which vertex arrived first, and establishes a strong yes for the random nearest neighbor model on the $d$-dimensional torus. It shows that an efficient algorithm given the unlabeled tree together with its embedding, or just its edge lengths, can return a confidence set of size independent of $n$ that contains the root with probability at least $1-\\varepsilon$. In one dimension the result is sharp: the required set size is $\\Theta(\\log(1/\\varepsilon)/\\log\\log(1/\\varepsilon))$, exponentially smaller than the known bounds for uniform and preferential attachment trees. In $d \\ge 2$ the paper gives an efficient algorithm with subpolynomial-in-$1/\\varepsilon$ confidence set size and an information-theoretic lower bound. If correct, geometry turns root finding from a search over a growing tree into a search over a small neighborhood of a few early long edges.","feed_headline":"In 1-D, root finding needs only ~log(1/eps)/loglog(1/eps) candidates","feed_subtitle":"Matching upper and lower bounds prove geometry shrinks the search to ~log(1/eps)/loglog(1/eps) candidates.","key_machinery":"The load-bearing objects are long edges and the induced subgraph of uncovered vertices. An edge is long when its torus length exceeds a threshold $\\ell$ chosen as a function of $\\varepsilon$; in $d=1$ an edge covers the interval between its endpoints, and a vertex is uncovered if no edge interval contains it, while in $d \\ge 2$ an edge covers a forbidden region of points closer to both endpoints than the edge length, and vertices falling there, or in their subtrees, are covered. The uncovered subgraph always contains the root, is a path in $d=1$, and has maximum degree bounded by a constant depending only on $d$ (Lemma 5.1). The algorithms return the uncovered vertices within graph distance $k$ of an edge longer than $\\ell$; the size bound comes from packing disjoint balls around long edges and the bounded degree of the uncovered subgraph, while correctness comes from the high probability that a long edge appears among the first $k$ edges and that the root is close to it. The lower bounds use the MLE posterior over feasible arrival-order permutations on specially constructed path-like tree families.","core_discovery":"The central claim is that geometric information about a random nearest neighbor tree localizes the root almost completely. For $d=1$, the paper proves matching upper and lower bounds: there is an $O(n^2 + \\log^2(1/\\varepsilon))$-time embedded root finding algorithm returning a confidence set with $|H| \\log|H| \\le c_1 \\log(1/\\varepsilon)$, and no algorithm can guarantee $|H| \\log|H| < c_2 \\log(1/\\varepsilon)$; equivalently the optimal set size is $\\Theta(\\log(1/\\varepsilon)/\\log\\log(1/\\varepsilon))$. The upper bound works by showing that with high probability one of the first $k \\approx \\log(1/\\varepsilon)$ edges is long, that the root lies within graph distance $O(\\log k)$ of such an edge in the subgraph of uncovered vertices, and that this subgraph has bounded degree, so a radius-$k$ exploration around all long edges has size only subpolynomial in $1/\\varepsilon$. For $d \\ge 2$ the same long-edge and uncovered-vertex strategy yields an efficient algorithm with confidence set size $\\exp(\\log(1/\\varepsilon)/(\\log\\log(1/\\varepsilon) + d\\log\\log(1/\\varepsilon)))$ and an impossibility result of the form $|H| \\log(|H|^{(d-1)/d}) \\ge c \\log(1/\\varepsilon)/d$. The lower bounds rest on families of path-like configurations that occur with probability at least $\\varepsilon$ and in which the root has lower posterior probability than at least $K(\\varepsilon)$ other vertices, so any $K(\\varepsilon)$-sized confidence set must fail.","pith_inferences":["Editorial inference: the same long-edge heuristic should transfer to other geometric growth models such as geometric preferential attachment, where early edges are also expected to be atypically long, potentially keeping confidence sets small.","Editorial inference: because both the positive algorithms and the lower-bound families use edge lengths or embeddings, the graph root finding variant (adjacency matrix only) may require substantially larger confidence sets or be impossible for geometric models.","Editorial inference: the thin-strip corollary suggests that effective dimension, not ambient dimension, controls the $\\log(1/\\varepsilon)$ bound; testing strip heights between $O(\\varepsilon^5)$ and $O(1)$ could reveal where the one-dimensional behavior breaks down.","Editorial inference: the paper's $d \\ge 2$ lower bound uses path-like configurations, but richer geometric families, such as branching or curved paths, might push the lower bound closer to the subpolynomial upper bound."],"forward_implications":["In $d=1$, the confidence set size becomes logarithmic in $1/\\varepsilon$ instead of subpolynomial, so geometric information makes root finding exponentially more efficient than in uniform or preferential attachment trees.","The 1-D algorithm runs in $O(n^2 + \\log^2(1/\\varepsilon))$ time and needs only the unlabeled embedded tree, so it can be applied directly to a snapshot of a growing geometric network without labels or arrival times.","For $d \\ge 2$, the paper's algorithm still returns a confidence set whose size is uniformly bounded in $n$ and subpolynomial in $1/\\varepsilon$, matching the current best known upper bound for uniform attachment trees.","Metric root finding, using only edge lengths, already gives an $O(n)$-time algorithm with confidence set size at most $2^d/\\varepsilon$, and with high probability every returned vertex arrived within the first $\\exp(cd)(1/\\varepsilon)\\log(1/\\varepsilon)$ steps.","The $d=1$ bounds carry over to a thin two-dimensional strip of height $O(\\varepsilon^5)$, so quasi-one-dimensional geometry is enough to obtain the logarithmic bound."],"supporting_citations":[{"why":"introduces the root finding problem and the MLE-based lower-bound technique, and gives the subpolynomial bounds for uniform and preferential attachment that this paper compares against","marker":"[BDL17]"},{"why":"studies combinatorial properties of the random nearest neighbor tree on the torus, establishes the $\\Theta(\\log n)$ degree scale, and raises the root-finding question the paper answers","marker":"[LM24]"},{"why":"introduces the random nearest neighbor (online nearest neighbor) model that defines the process studied here","marker":"[Ste89]"},{"why":"shows that for some random tree models $n$-independent confidence sets are impossible, providing the contrast that makes the geometric $n$-independent bounds significant","marker":"[BDG22]"},{"why":"supplies the cone-covering lemma (Lemma 5.5) used to prove that vertices in the metric confidence set arrived early","marker":"[DGL13]"},{"why":"provides the Voronoi-cell diameter observation used in the same early-arrival proof for metric root finding","marker":"[DGL W17]"},{"why":"develops limit theory for the on-line nearest-neighbour graph, supporting the paper's observation that much sharper statements are available in $d=1$ than in higher dimensions","marker":"[PW06]"}],"fun_headline_variants":["Matching bounds shrink 1-D root search to loglog scale","1-D tree roots found with ~log(1/eps)/loglog(1/eps) candidates","Tight confidence set: 1-D root needs loglog(1/eps) candidates","Geometry trims root hunt to loglog(1/eps) size in 1-D"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the $d \\ge 2$ upper bound, the correctness proof relies on the unproved assertion that whenever one of the first $k$ edges is long, the root is within graph distance $7\\log k$ of that edge in the bounded-degree uncovered subgraph; if that proximity claim fails, the algorithm's confidence set can miss the root.","fun_headline_variants_meta":{"raw":{"variants":["Matching bounds shrink 1-D root search to loglog scale","1-D tree roots found with ~log(1/eps)/loglog(1/eps) candidates","Tight confidence set: 1-D root needs loglog(1/eps) candidates","Geometry trims root hunt to loglog(1/eps) size in 1-D"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000547,"raw_usage":{"total_tokens":2743,"prompt_tokens":1199,"completion_tokens":1544,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":815,"completion_tokens_details":{"reasoning_tokens":1451}},"tokens_in":815,"tokens_out":1544,"duration_ms":11639,"temperature":1.0,"reasoning_tokens":1451,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:18:08.509036+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate 2-NN trees on the unit torus for large $n$ and small $\\varepsilon$; among the first $k = \\gamma \\log(1/\\varepsilon)$ edges, find the first edge of length at least $\\ell = (C(d)\\,\\gamma\\, e^{1/\\gamma} \\log(1/\\varepsilon))^{-1/d}$ and measure the graph distance in the uncovered subgraph from the earlier endpoint of that edge to vertex 1. If this distance exceeds $7\\log k$ with non-negligible probability for some $\\varepsilon$, the correctness claim behind Lemma 5.2 fails.","supporting_citations":[],"review_version":1}