Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
A Tight Analysis of Khatri-Rao Oblivious Subspace Embeddings
Lorenzo Beretta, Cameron Musco
We study random sketching matrices with Khatri-Rao structure. In particular, we consider the Khatri-Rao product (i.e., column-wise tensor product) $A_1\odot\cdots\odot A_d \in \mat…
cs.DS2025
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…
cs.DS2025
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…