48 citations · 102 across the 15 of their papers we have counts for
Showing 2022Show all
3 papers · 1 filter
cs.DS2022★ 1 cited
Optimal Query Complexities for Dynamic Trace Estimation
David P. Woodruff, Fred Zhang, Qiuyi Zhang
We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly…
cs.DS2022
Online Prediction in Sub-linear Space
Binghui Peng, Fred Zhang
We provide the first sub-linear space and sub-linear regret algorithm for online learning with expert advice (against an oblivious adversary), addressing an open question raised re…
cs.DS2022★ 4 cited
Faster Fundamental Graph Algorithms via Learned Predictions
Justin Y. Chen, Sandeep Silwal, Ali Vakilian +1
We consider the question of speeding up classic graph algorithms with machine-learned predictions. In this model, algorithms are furnished with extra advice learned from past or si…