169 citations · 169 across the 12 of their papers we have counts for
3 papers · 1 filter
Reusing Samples in Variance Reduction
Yujia Jin, Ishani Karmarkar, Aaron Sidford +1
We provide a general framework to improve trade-offs between the number of full batch and sample queries used to solve structured optimization problems. Our results apply to a broa…
Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
Yujia Jin, Ishani Karmarkar, Christopher Musco +2
We consider the problem of estimating the spectral density of the normalized adjacency matrix of an -node undirected graph. We provide a randomized algorithm that, with $O(nε^{-…
Towards Optimal Effective Resistance Estimation
Rajat Vadiraj Dwaraknath, Ishani Karmarkar, Aaron Sidford
We provide new algorithms and conditional hardness for the problem of estimating effective resistances in -node -edge undirected, expander graphs. We provide an $\widetilde{O…