REVIEW 2 cited by
Optimal root recovery for uniform attachment trees and $d$-regular growing trees
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We consider root-finding algorithms for random rooted trees grown by uniform attachment. Given an unlabeled copy of the tree and a target accuracy $\varepsilon > 0$, such an algorithm outputs a set of nodes that contains the root with probability at least $1 - \varepsilon$. We focus on the algorithm introduced by Bubeck, Devroye and Lugosi (2017) and proved to be optimal by Crane and Xu (2021). We prove that, for the optimal algorithm, an output set of size $\exp(O(\log^{1/2}(1/\varepsilon)))$ suffices; this bound is sharp and answers a question of Bubeck, Devroye and Lugosi (2017). We prove similar bounds for random regular trees that grow by uniform attachment, strengthening a result of Khim and Loh (2017).
Forward citations
Cited by 2 Pith papers
-
Finding Adam in noisy trees
A uniform random recursive tree polluted by an Erdős–Rényi graph with p=o(log n/n) still admits a root confidence set of size depending only on ε, not on n.
-
Subcritical percolation and network archaeology on random recursive tree substrate networks
For random recursive trees with independent Erdős–Rényi shortcut edges, subcritical bond percolation exposes a decorated tree structure on which Jordan centrality recovers the root within a deterministic-size confidence set.
Discussion (0). Continue with ORCID to comment.