Showing cs.DSShow all
3 papers · 1 filter
cs.DS2024
Approximating the Top Eigenvector in Random Order Streams
Praneeth Kacham, David P. Woodruff
When rows of an matrix are given in a stream, we study algorithms for approximating the top eigenvector of the matrix (equivalently, the top right singula…
cs.DS2024
High-Dimensional Geometric Streaming for Nearly Low Rank Data
Hossein Esfandiari, Vahab Mirrokni, Praneeth Kacham +2
We study streaming algorithms for the subspace approximation problem. Given points as an insertion-only stream and a rank parameter , the su…
cs.DS2024
Optimal Communication for Classic Functions in the Coordinator Model and Beyond
Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni +2
In the coordinator model of communication with servers, given an arbitrary non-negative function , we study the problem of approximating the sum up…