13 citations · 21 across the 18 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2022
Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs
Jonathan A. Kelner, Frederic Koehler, Raghu Meka +1
Sparse linear regression with ill-conditioned Gaussian random designs is widely believed to exhibit a statistical/computational gap, but there is surprisingly little formal evidenc…
cs.DS2019
Near-Optimal Bounds for Online Caching with Machine Learned Advice
Dhruv Rohatgi
In the model of online caching with machine learned advice, introduced by Lykouris and Vassilvitskii, the goal is to solve the caching problem with an online algorithm that has acc…
cs.DS2018
Sliding window order statistics in sublinear space
Dhruv Rohatgi
We extend the multi-pass streaming model to sliding window problems, and address the problem of computing order statistics on fixed-size sliding windows, in the multi-pass streamin…