# Optimal root recovery for uniform attachment trees and d-regular growing trees

arXiv: https://arxiv.org/abs/2411.18614 · HTML: https://mlsanity.com/paper/2411.18614/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2024.

## Built on by (most cited first, 1 of 1)

- [History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities](https://mlsanity.com/paper/2606.24465/) (2026)

## Abstract (arXiv)

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(log1/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).