16 citations · 62 across the 29 of their papers we have counts for
Showing 2019Show all
2 papers · 1 filter
cs.DS2019
Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation
Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff
Recently, Musco and Woodruff (FOCS, 2017) showed that given an positive semidefinite (PSD) matrix , it is possible to compute a -approximate relative-error l…
cs.DS2019
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams
Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff
We study the Maximum Independent Set problem for geometric objects given in the data stream model. A set of geometric objects is said to be independent if the objects are pairwise…