3 papers
cs.LG2026
Adaptive Weighted Averaging
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar +1
We study the problem of selecting the largest among unknown values given only a single unbiased estimate for each . We design strategies that are sim…
cs.DS2024
New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
Aditya Bhaskara, Eric Evert, Vaidehi Srinivas +1
We develop new techniques for proving lower bounds on the least singular value of random matrices with limited randomness. The matrices we consider have entries that are given by p…
cs.CG2023
On Mergable Coresets for Polytope Distance
Benwei Shi, Aditya Bhaskara, Wai Ming Tai +1
We show that a constant-size constant-error coreset for polytope distance is simple to maintain under merges of coresets. However, increasing the size cannot improve the error boun…