6 citations · 6 across the 13 of their papers we have counts for
14 papers
Finding Adam in noisy trees
Luc Devroye, Gábor Lugosi, Neeladri Maitra
We consider the problem of finding the root vertex of a random uniform attachment tree, when the union of the unlabeled tree and an Erdős-Rényi random graph is ob…
The temporal stochastic block model
Sofiya Burova, Gábor Lugosi, Guillem Perarnau
Motivated by the need to understand infection spreading in inhomogeneous populations, we consider a \emph{temporal} version of the stochastic block model, where each edge is equipp…
Testing properties of trees in graphical models with covariance queries
Sofiya Burova, Francisco Calvillo, Gábor Lugosi +1
We consider the problem of testing properties of graphs underlying high-dimensional graphical models. We adopt the model of covariance queries introduced by Lugosi, Truszkowski, Ve…
Ratio Covers of Convex Sets and Optimal Mixture Density Estimation
Spencer Compton, Gábor Lugosi, Jaouad Mourtada +2
We study density estimation in Kullback-Leibler divergence: given an i.i.d. sample from an unknown density , the goal is to construct an estimator such that…
A study of centrality measures in random recursive trees
Richard Coll Josifov, Luc Devroye, Gabor Lugosi
We investigate the behaviour of five classical centrality measures--Jordan, rumor, betweenness, degree, and closeness centralities--in the setting of uniform random recursive trees…
The statistical threshold for planted matchings and spanning trees
Louigi Addario-Berry, Omer Angel, Gábor Lugosi +2
In this paper, we study the problem of detecting the presence of a planted perfect matching or spanning tree in an Erdős--Rényi random graph. More precisely, we study the hypothesi…
Robust, sub-Gaussian mean estimators in metric spaces
Daniel Bartl, Gabor Lugosi, Roberto Imbuzeiro Oliveira +1
Estimating the mean of a random vector from i.i.d. data has received considerable attention, and the optimal accuracy one may achieve with a given confidence is fairly well underst…
Temporal connectivity of Random Geometric Graphs
Anna Brandenberger, Serte Donderwinkel, Céline Kerriou +2
A temporal random geometric graph is a random geometric graph in which all edges are endowed with a uniformly random time-stamp, representing the time of interaction between vertic…
Leaf Stripping on Uniform Attachment Trees
Louigi Addario-Berry, Anna Brandenberger, Simon Briend +2
In this note we analyze the performance of a simple root-finding algorithm in uniform attachment trees. The leaf-stripping algorithm recursively removes all leaves of the tree for…
The top eigenvalue of uniformly random trees
Louigi Addario-Berry, Gábor Lugosi, Roberto Imbuzeiro Oliveira
Let be a uniformly random tree with vertex set , let be the largest vertex degree in , and let $λ_1({\mathbf…
Random friend trees
Louigi Addario Berry, Simon Briend, Luc Devroye +3
We study a random recursive tree model featuring complete redirection called the random friend tree and introduced by Saramäki and Kaski. Vertices are attached in a sequential mann…
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…
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…
Sharp threshold for percolation on expanders
Itai Benjamini, Stéphane Boucheron, Gábor Lugosi +1
We study the appearance of the giant component in random subgraphs of a given large finite graph G=(V,E) in which each edge is present independently with probability p. We show tha…