11 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…
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 hypothe…