5 papers
History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities
Johannes Bäumler, Simon Briend, Joost Jorritsma
We study the problem of estimating the arrival times of vertices in a uniform random recursive tree from its unlabeled structure. We adopt a pointwise perspective and analyze the d…
Does freezing impede the growth of random recursive trees?
Anna Brandenberger, Simon Briend, Hannah Cairns +2
Uniform attachment with freezing is an extension of the classical model of random recursive trees, in which trees are recursively built by attaching new vertices to old ones. In th…
On the quality of randomized approximations of Tukey's depth
Simon Briend, Gábor Lugosi, Roberto Imbuzeiro Oliveira
Tukey's depth (or halfspace depth) is a widely used measure of centrality for multivariate data. However, exact computation of Tukey's depth is known to be a hard problem in high d…
Broadcasting in random recursive dags
Simon Briend, Luc Devroye, Gabor Lugosi
A uniform -{\sc dag} generalizes the uniform random recursive tree by picking parents uniformly at random from the existing nodes. It starts with ''roots''. Each of the…
Estimating the history of a random recursive tree
Simon Briend, Christophe Giraud, Gábor Lugosi +1
This paper studies the problem of estimating the order of arrival of the vertices in a random recursive tree. Specifically, we study two fundamental models: the uniform attachment…