5 papers
Geometric planted matchings beyond the Gaussian model
Lucas da Rocha Schwengber, Roberto Imbuzeiro Oliveira
We consider the problem of recovering an unknown matching between a set of randomly placed points in and random perturbations of these points. This can be seen a…
Mean Testing under Truncation beyond Gaussian
Yuhao Wang, Roberto Imbuzeiro Oliveira, Themis Gouleakis
We characterize the fundamental limits of high-dimensional mean testing under arbitrary truncation, where samples are drawn from the conditional distribution for…
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…
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…
Counting communities in weighted Stochastic Block Models via semidefinite programming
Deborah Oliveira, Andressa Cerqueira, Roberto Oliveira
We consider the problem of estimating the number of communities in a weighted balanced Stochastic Block Model. We construct hypothesis tests based on semidefinite programming and w…