EUVIMEDEUVIMED entdecken
Crossref

Finding the Root in Random Nearest Neighbor Trees

Anna Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan

Random Structures & Algorithms · 2026-03 · 68 (2)

DOI: 10.1002/rsa.70057 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 24.03.2026. Verfasst von Anna Brandenberger und 3 weiteren Autor:innen. Die Arbeit nennt 22 Literaturangaben. Gefördert von: NSF, ARO.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the inference of the root for a random nearest neighbor tree generated by sequentially embedding vertices uniformly at random in the ‐dimensional torus and connecting each new vertex to the nearest existing vertex. Given an error parameter and the unlabeled tree, we want to efficiently find a small “confidence set” of candidate vertices containing the root with probability at least . 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 and the information‐theoretic lower bound is polylogarithmic in . For embedded root finding in , we obtain matching upper and lower bounds for a confidence set of size .

Förderung

  • NSF
  • ARO

Zitieren

APA

Brandenberger, A., Marcussen, C., Mossel, E., & Sudan, M. (2026). Finding the Root in Random Nearest Neighbor Trees. Random Structures & Algorithms, 68(2). https://doi.org/10.1002/rsa.70057

Vancouver

Brandenberger A, Marcussen C, Mossel E, Sudan M. Finding the Root in Random Nearest Neighbor Trees. Random Structures & Algorithms. 2026;68(2). doi:10.1002/rsa.70057

BibTeX
@article{Brandenberger2026,
  author = {Brandenberger, Anna and Marcussen, Cassandra and Mossel, Elchanan and Sudan, Madhu},
  title = {Finding the Root in Random Nearest Neighbor Trees},
  journal = {Random Structures & Algorithms},
  year = {2026},
  volume = {68},
  number = {2},
  doi = {10.1002/rsa.70057}
}
Kostenlos starten →