Finding the Root in Random Nearest Neighbor Trees

We study the inference of the root for a random nearest neighbor tree generated by sequentially embedding vertices uniformly at random in the d$$ d $$ ‐dimensional torus and connecting each new vertex to the nearest existing vertex. Given an error parameter ε>0$$ \varepsilon >0 $$ and the unlabeled tree, we want to efficiently find a small “confidence set” of candidate vertices containing the root with probability at least 1−ε$$ 1-\varepsilon $$ . We define several problem variations‐such as embedded and metric root finding‐which differ based on the available metric information provided in addition to the graph structure (torus embedding, edge lengths, or none). For embedded and metric root finding, we construct efficient algorithms and derive bounds on the confidence set size. For embedded root finding, the upper bound is subpolynomial in 1/ε$$ 1/\varepsilon $$ and the information‐theoretic lower bound is polylogarithmic in 1/ε$$ 1/\varepsilon $$ . For embedded root finding in d=1$$ d=1 $$ , we obtain matching upper and lower bounds for a confidence set of size Θlog(1/ε)loglog(1/ε)$$ \Theta \left(\frac{\log \left(1/\varepsilon \right)}{\mathrm{loglog}\left(1/\varepsilon \right)}\right) $$ .