4 papers
Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
Lorenzo Beretta, Deeparnab Chakrabarty, C. Seshadhri
We revisit the problem of designing sublinear algorithms for estimating the average degree of an -vertex graph. The standard access model for graphs allows for the following que…
Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram +1
We give a reduction from -approximate Earth Mover's Distance (EMD) to -approximate Closest Pair (CP). As a consequence, we improve the fastest kno…
Sketched Lanczos uncertainty score: a low-memory summary of the Fisher information
Marco Miani, Lorenzo Beretta, Søren Hauberg
Current uncertainty quantification is memory and compute expensive, which hinders practical uptake. To counter, we develop Sketched Lanczos Uncertainty (SLU): an architecture-agnos…
Multi-Swap -Means++
Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi +1
The -means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is often the practitioners' choice algorithm for optimizing the popular -means clustering objective and is know…