Showing 2024Show all
3 papers · 1 filter
cs.DS2024
Tight Sampling Bounds for Eigenvalue Approximation
William Swartworth, David P. Woodruff
We consider the problem of estimating the spectrum of a symmetric bounded entry (not necessarily PSD) matrix via entrywise sampling. This problem was introduced by [Bhattacharjee,…
cs.DS2024
Fast Sampling Based Sketches for Tensors
William Swartworth, David P. Woodruff
We introduce a new approach for applying sampling-based sketches to two and three mode tensors. We illustrate our technique to construct sketches for the classical problems of $\el…
cs.DS2024
Improving the Bit Complexity of Communication for Distributed Convex Optimization
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan +3
We consider the communication complexity of some fundamental convex optimization problems in the point-to-point (coordinator) and blackboard communication models. We strengthen kno…