{"id":"7d32baf8-45d0-43a8-a828-69c8c83b899a","arxiv_id":"2411.18614","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For uniform attachment trees, the optimal root-finding output size is exp(Theta(sqrt(log(1/epsilon)))), matching the known lower bound and resolving an open question.","lead":"This paper proves that for random trees built by uniform attachment, the best root-finding algorithm can find the root with error epsilon using roughly e to the power of the square root of log(1/epsilon) guesses, and that no algorithm can do better. It answers an open question from 2017 and gives the same bound for d-regular growing trees.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.1's all-n failure bound is not derived: Section 4.4 proves only a limsup bound, and no quantitative rate or monotonicity bridges the finite-n range.","rationale":"The reader identified the limsup-to-all-n promotion as the weakest assumption, and my reading of Section 4.4 confirms that this is the load-bearing gap. The proof of Theorem 1.1 shows limsup_n P(|B_n| >= threshold) <= (8+C)epsilon, but the theorem requires the same bound for every n. Bridging this gap needs either a monotonicity argument, or an explicit quantitative rate showing that the asymptotic regime begins before K(epsilon), or a separate finite-n argument. None is present. The same issue affects Theorem 1.2, whose proof in Section 1.1 also relies on limsup statements from Lemmas 3.3 and Proposition 3.6. I do not see a more fundamental flaw in the asymptotic strategy: the central arguments around the competitive ratio, the flow bounds, and the Pólya-urn descriptions appear coherent, and the claimed exponential-in-sqrt(log(1/epsilon)) size is plausible. The omitted lower-bound construction for Theorem 1.2 is a completeness issue, but it is secondary to the all-n gap because the theorem statement itself only asserts the upper bound. Since the reader already set CONDITIONAL, and my concern is the same one, the verdict should remain unchanged: the paper should be accepted only conditionally, pending a proof that the limsup bounds can be converted into the stated all-n bounds.","tokens_in":30711,"tokens_out":4960,"duration_ms":57434,"concrete_test":"Derive an explicit quantitative threshold n0(epsilon) for the event E(n,epsilon) in Section 4.4, using finite-n concentration bounds for the Pólya-urn convergences behind Lemmas 4.2 and Propositions 4.5 and 4.7. Then check whether n0(epsilon) can be bounded by K(epsilon)=C* exp(c* sqrt(log(1/epsilon))) after enlarging C* and c*. If no such bound is obtainable, the all-n assertion of Theorem 1.1 is not proved by the written argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1.1 asserts P(root not in A_K(T_n)) <= epsilon for every n, but the proof in Section 4.4 concludes with limsup bounds. Specifically, the proof obtains limsup_n P(E(n,epsilon)^c) <= (C+6)epsilon and then limsup_n P(|B_n| >= ... ) <= (8+C)epsilon, and says the result follows because the root is found whenever K >= |B_n|. A limsup inequality only guarantees the bound for all sufficiently large n, say n >= n0(epsilon), with n0 depending on the almost-sure convergence of the Pólya-urn proportions used in Lemmas 4.2 and Propositions 4.5 and 4.7. No quantitative rate for this convergence is supplied, so n0(epsilon) could exceed K(epsilon)=C* exp(c* sqrt(log(1/epsilon))) for the chosen constants. For n with K(epsilon) < n < n0(epsilon), the proof gives no control, and the K(epsilon)>=n trivial case does not apply. The same limsup-to-all-n gap appears in the proof of Theorem 1.2 (Section 1.1 uses Lemma 3.3 and Proposition 3.6, both stated as limsup bounds). This is not an internal inconsistency, but as written the central theorem is stronger than what the proof establishes.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies root-finding for two families of random trees: uniform attachment (UA) and d-regular uniform attachment (UAd). For the centrality-based algorithm A_k of Bubeck, Devroye and Lugosi, it claims that an output set of size K(eps)=C* exp(c* sqrt(log(1/eps))) recovers the root with probability at least 1-eps, uniformly in the tree size n, for UA(n); an analogous statement holds for UAd(n) with d-dependent constants. The proof strategy is to bound the number of nodes at least as central as the root by combining a deterministic bound on the competitive ratio, a deterministic or probabilistic count of 'competitors' in small subtrees, and a tail bound for the count set N_x(P) built from the asymptotic subtree proportions P_u. The paper also sketches an argument to make the UAd constants independent of d.","tokens_in":30983,"tokens_out":10341,"duration_ms":93232,"significance":"If the main upper bounds are correct, Theorem 1.1 resolves the open question from Bubeck, Devroye and Lugosi (2017) by matching their lower bound up to the constant in the exponent. The paper's technical machinery, especially the nested Polya-urn description of subtree proportions (Propositions 3.1 and 4.1), the flow-counting bound (Proposition 2.4), and the probabilistic tail bound for N_x(P) (Proposition 4.5), is substantial and likely to be useful beyond this paper. The authors are careful with distributional identities and do not fit parameters to data; the lower bound for UA is external, and the optimality theorem of Crane and Xu is used as a black box. The main reservation is that both main theorems are stated for every n, while the written proofs deliver only limsup estimates.","major_comments":[{"comment":"The proof establishes only limsup bounds, not the stated all-n bound. Equations (4.7) and (4.8) are limsup estimates, and the final displayed inequality is of the form limsup_n P(|B_n| >= ...) <= (8+C)eps. The theorem asserts P(root not in A_K(T_n)) <= eps for every n. The passage from finite-n subtree counts to the limiting quantities P_u relies on almost-sure convergence |theta_u T_n|/n -> P_u, so the limsup bound holds only for n >= n_0(eps); no quantitative rate or monotonicity is supplied, and the intermediate values K(eps) < n < n_0(eps) are uncontrolled. The text explicitly says it avoids proving rate-of-convergence bounds, which confirms that this is not merely a presentational issue.","section":"Section 4.4 (Proof of Theorem 1.1)"},{"comment":"The proof of Theorem 1.2 concludes an all-n probability bound from Lemma 3.3 and Proposition 3.6, but both are stated only as limsup bounds. In the displayed computation P(|B_n| >= ...) <= P(D >= log_{3/2}(1/eps)) + P(Phi(T_n) >= eps^{-1/a}), the two summands are limsup bounds, not uniform-in-n bounds. The random time n_0 in the proof of Proposition 3.6 depends on almost-sure convergence of |theta_u T_n|/n to P_u, and no quantitative control is given. Thus Theorem 1.2, as stated for all n in N_1, is not derived.","section":"Section 1.1 (Proof of Theorem 1.2)"},{"comment":"The optimality claim for the d-regular model, namely that 'the bound in Theorem 1.2 is optimal up to the value of c_d^*', is supported only by a reference to an adaptation of a construction from [7] whose details are omitted. Since the lower bound in [7] is for the UA model, not for UAd, this is not a direct citation. The theorem's optimality assertion is therefore not established in the manuscript. Please either provide the construction or modify the claim.","section":"Section 1, paragraph after Theorem 1.2"}],"minor_comments":[{"comment":"The text contains the typo 'Lemmma 4.9'; it should read 'Lemma 4.9'.","section":"Section 4.5"},{"comment":"The text refers to 'Remark 3.4', but Section 3.4 is not a remark; the cross-reference should be corrected.","section":"Section 4.5"},{"comment":"The constant c is reused with different meanings in Lemma 4.6, Proposition 2.4, and the final inequality of Proposition 4.5; using distinct labels such as c_1, c_2, c_3 consistently would improve readability.","section":"Proof of Proposition 4.5"}],"recommendation":"major_revision","confidential_remarks":"The all-n versus limsup gap is the main obstacle to accepting the paper in its current form. I believe it is fixable, either by adding a quantitative concentration argument or by weakening the theorem statements to limsup statements, but as written the main theorems are stronger than what the proofs deliver. The omitted d-regular lower bound and the sketch in Section 4.5 should also be addressed. If the gap is closed, the paper would be a strong contribution to the root-finding literature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things worth knowing about arXiv:2411.18614. First, the headline result is almost certainly right: the optimal Bubeck–Devroye–Lugosi algorithm can find the root in a uniform attachment tree with output size exp(O(sqrt(log(1/epsilon)))), matching the known lower bound up to constants and resolving their 2017 question. Second, the proof as written does not prove the theorem as stated. Both Theorem 1.1 and Theorem 1.2 claim all-n bounds, but the arguments in Sections 4.4 and 1.1 conclude with limsup bounds and no uniform-in-n or quantitative rate is supplied. For Theorem 1.1, the final step is literally: limsup P(|B_n| >= threshold) <= (8+C)epsilon, then \"since K >= |B_n| ... the desired result follows.\" That jump is invalid. The same gap is in Theorem 1.2 via Lemma 3.3 and Prop 3.6. This is fixable—either prove quantitative convergence for the relevant urn limits or state the theorems with \"for all sufficiently large n\"—but as written the central claims are stronger than the arguments.\n\nWhat's good: the upper-bound machinery is real. Competitive ratio with polynomial tails, deterministic control of competitor count in small subtrees via preflows and a non-asymptotic Hardy–Ramanujan partition bound, and for UA a probabilistic replacement (Prop 4.5) built from nested Pólya urns and a comparison to a gamma flow. The proof of Prop 4.5, with the random bijection and the geometric branching process, is the most interesting part of the paper and is done carefully. No fitting, no circularity; external lower bounds from BDL and optimality from Crane–Xu are used honestly. The d-regular improvement over Khim–Loh is significant, though the claimed lower bound for that case is only described as \"tedious but no new ideas\" and omitted—so the optimality half of Theorem 1.2 isn't actually in the paper.\n\nWho should read it: anyone working on network archaeology, source detection, or random growing-tree asymptotics. The techniques are transferable, and the gap is instructive for anyone writing finite-n statements from almost-sure limits. I'd send it to a serious referee, but I'd insist the revision either upgrade the proofs to genuine all-n bounds or downgrade the theorems to limsup/eventual statements, and either include the d-regular lower bound or flag it as omitted.","headline":"The main result is very likely correct and the proof machinery is impressive, but the theorems assert all-n bounds while the written proofs only establish limsup bounds, so the paper needs a revision before the claims as stated are reliable.","tokens_in":31521,"tokens_out":4382,"would_cite":true,"duration_ms":40716,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60C05","05C80","62M05","94C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the optimal root-finding algorithm can return a candidate set of size $\\\\exp(O(\\\\sqrt{\\\\log(1/\\\\varepsilon)}))$ while keeping failure probability below $\\\\varepsilon$ for uniform attachment and $d$-regular growing…","keywords":["uniform attachment tree","random recursive tree","rumor centrality","root reconstruction","network archaeology","d-regular growing tree","competitive ratio","Pólya urn"],"falsifier":"Run the centrality algorithm on uniform attachment trees of many sizes n for fixed epsilon and the constants C*, c*; if any single n yields a failure probability above epsilon (within simulation error), the theorem's 'for all n' statement fails. The analogous check for d-regular trees settles Theorem 1.2.","tokens_in":30542,"feed_emoji":"🌳","tokens_out":10319,"duration_ms":89871,"temperature":0.7,"pith_summary":"This paper aims to settle the size–error tradeoff for root finding in uniform attachment trees and $d$-regular growing trees. It proves that the centrality-based algorithm that outputs the nodes with the smallest product-of-subtree-sizes needs at most $K=C_*\\\\exp(c_*\\\\sqrt{\\\\log(1/\\\\varepsilon)})$ nodes to contain the true root with probability at least $1-\\\\varepsilon$, for every tree size $n$. Because an earlier lower bound [7] showed no algorithm can use substantially fewer nodes, this identifies the optimal candidate-set size up to constant factors and answers the open question posed there. For $d$-regular uniform attachment trees the same rate holds, improving the earlier $O(1/\\\\varepsilon)$ bound [15]; the paper also sketches how to remove the $d$-dependence of the constant in the exponential.","feed_headline":"Root recovery: exp(O(sqrt(log(1/ε)))) candidate nodes suffice","feed_subtitle":"For uniform attachment and d-regular trees, this set contains the root with probability 1-ε, matching the lower bound.","key_machinery":"The argument is carried by three quantitative ingredients. First, the 'heavy' nodes—those whose rooted subtree contains at least a third of the tree—have exponentially decaying depth/weight tails (Lemma 3.3 and Lemma 4.2). Second, the competitive ratio $\\\\Phi(T)=\\\\varphi_T(\\\\emptyset)/\\\\min_u\\\\varphi_T(u)$ has polynomial upper tails (Proposition 3.6 and Proposition 4.7). Third, inside any small subtree the number of nodes more central than the root is $\\\\exp(O(\\\\sqrt{\\\\log\\\\Phi(T)}))$ (Proposition 3.5) in the deterministic $d$-ary setting, and a probabilistic analogue (Proposition 4.5) in the unbounded-degree UA setting. The counting uses a 'preflow' $p(u)=|\\\\theta_u T|/|T|$ compared with the geometrically decaying flow $\\\\gamma(u)=\\\\alpha^{-\\\\sum_i(u_i-1)}$; the count $N_x(\\\\gamma)$ is controlled by a non-asymptotic partition-counting bound [12]. In the UA case the random flow coming from a Pólya-urn representation is stochastically dominated by such a geometric flow through an explicit random bijection, and the multiplicities behave like Geometric random variables in the number of non-first-born ancestors.","core_discovery":"The paper's central claim is that the lower bound from [7] is tight. Define the centrality $\\\\varphi_T(u)=\\\\prod_{v\\\\ne u}|(T,u)_{v\\\\downarrow}|$; the algorithm $A_k$ returns the $k$ nodes of smallest $\\\\varphi_T$. The paper shows that for $K=C_*\\\\exp(c_*\\\\sqrt{\\\\log(1/\\\\varepsilon)})$, we have $\\\\mathbb{P}(\\\\emptyset\\\\notin A_K(T_n))\\\\le\\\\varepsilon$ for every $n$, both when $T_n\\\\sim\\\\mathrm{UA}(n)$ (Theorem 1.1) and when $T_n\\\\sim\\\\mathrm{UA}_d(n)$ (Theorem 1.2, with constants depending on $d$, and a sketched argument for a universal constant). Since $A_k$ is known [10] to have minimal error among size-$k$ algorithms, the size of the candidate set is optimal up to constants. The proof works by bounding the random set $B_n=\\\\{v:\\\\varphi_{T_n}(v)\\\\le\\\\varphi_{T_n}(\\\\emptyset)\\\\}$ of nodes at least as central as the root.","pith_inferences":["The proofs are mostly asymptotic in nature; if one wants a fully uniform-in-$n$ theorem, the missing step would be to control the rate at which subtree proportions converge to their Pólya-urn limits, so intermediate-$n$ spikes in failure probability are not ruled out by the written argument.","The same proof template—exponential tails for heavy subtrees, polynomial tails for a competitive ratio, and a flow-counting bound—may transfer to other growing-tree models whose subtree proportions are built from independent stick-breaking variables; testing it on preferential attachment would be a concrete next step.","If the sketched removal of the $d$-dependence in Theorem 1.2 is filled in, the same bound with a universal constant would hold for all $d\\\\ge 3$ simultaneously, giving a single algorithm whose candidate-set size does not degrade with degree."],"forward_implications":["If Theorem 1.1 is correct, the size–error tradeoff for uniform attachment trees is known: no algorithm can beat $\\\\exp(\\\\Omega(\\\\sqrt{\\\\log(1/\\\\varepsilon)}))$ and $A_K$ achieves $\\\\exp(O(\\\\sqrt{\\\\log(1/\\\\varepsilon)}))$, up to constants.","The same rate for $d$-regular uniform attachment trees shows the earlier $O(1/\\\\varepsilon)$ confidence sets are far from optimal, and the near-optimal size is achieved by the same centrality ranking.","The tail bounds for the competitive ratio and for the depth/weight of heavy subtrees are model facts that can be reused when analyzing other inference tasks on these trees.","Because $A_k$ is optimal among size-$k$ algorithms, the result identifies the minimax candidate-set size, not just the performance of one heuristic."],"supporting_citations":[{"why":"The earlier paper that proved the lower bound, introduced the centrality algorithm, and posed the question this paper answers.","marker":"[7]"},{"why":"The paper that proved the centrality-based algorithm has minimal error among algorithms of a given size, making the size bound optimal.","marker":"[10]"},{"why":"The earlier d-regular-tree result giving O(1/epsilon) confidence sets, which Theorem 1.2 strengthens.","marker":"[15]"},{"why":"The non-asymptotic partition-counting bound used to control the number of nodes in the geometric-flow count.","marker":"[12]"},{"why":"The Pólya-urn Dirichlet limit theorem used for the asymptotic subtree proportions in the regular model.","marker":"[2]"},{"why":"The modern Pólya-urn convergence results used to justify the almost-sure limits of subtree proportions.","marker":"[8]"},{"why":"The branching-process fact used to describe the multiplicities Z_u as Geometric variables.","marker":"[14]"},{"why":"The stochastic-order comparison for Beta distributions used in the regular-tree tail bound.","marker":"[1]"},{"why":"The comparability result for special distributions used to stochastically bound Beta variables.","marker":"[16]"}],"fun_headline_variants":["Root recovery: exp(O(sqrt(log(1/ε)))) candidates suffice","Sharp bound: exp(O(sqrt(log(1/ε)))) candidate set","Optimal root finding: exp(O(sqrt(log(1/ε)))) nodes","Optimal root recovery: exp(O(sqrt(log(1/ε)))) suffices"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the bounds proved only in the limit as the tree size goes to infinity can be applied to every individual tree size; the paper does not supply the argument that would rule out isolated intermediate sizes where the failure probability spikes above the tolerance.","fun_headline_variants_meta":{"raw":{"variants":["Root recovery: exp(O(sqrt(log(1/ε)))) candidates suffice","Sharp bound: exp(O(sqrt(log(1/ε)))) candidate set","Optimal root finding: exp(O(sqrt(log(1/ε)))) nodes","Optimal root recovery: exp(O(sqrt(log(1/ε)))) suffices"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000717,"raw_usage":{"total_tokens":3220,"prompt_tokens":945,"completion_tokens":2275,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":2189}},"tokens_in":561,"tokens_out":2275,"duration_ms":16785,"temperature":1.0,"reasoning_tokens":2189,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:02:20.108788+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the centrality algorithm on uniform attachment trees of many sizes n for fixed epsilon and the constants C*, c*; if any single n yields a failure probability above epsilon (within simulation error), the theorem's 'for all n' statement fails. The analogous check for d-regular trees settles Theorem 1.2.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Pólya-urn Dirichlet limit theorem used for the asymptotic subtree proportions in the regular model."},{"cited_title":"Inference on the history of a randomly growing tree","cited_arxiv_id":null,"evidence_quote":"The paper that proved the centrality-based algorithm has minimal error among algorithms of a given size, making the size bound optimal."},{"cited_title":"Smoothing Equations for Large P´ olya Urns","cited_arxiv_id":null,"evidence_quote":"The modern Pólya-urn convergence results used to justify the almost-sure limits of subtree proportions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The branching-process fact used to describe the multiplicities Z_u as Geometric variables."},{"cited_title":"Convex transform order of beta distributions with some consequences","cited_arxiv_id":null,"evidence_quote":"The stochastic-order comparison for Beta distributions used in the regular-tree tail bound."},{"cited_title":"Comparability of special distributions","cited_arxiv_id":null,"evidence_quote":"The comparability result for special distributions used to stochastically bound Beta variables."}],"review_version":1}