1 citations · 2 across the 3 of their papers we have counts for
6 papers · 1 filter
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
Nadiia Chepurko, Kenneth L. Clarkson, Praneeth Kacham +1
In the numerical linear algebra community, it was suggested that to obtain nearly optimal bounds for various problems such as rank computation, finding a maximal linearly independe…
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh +2
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression that are comparable to their quantum analogues. De…
Testing Positive Semi-Definiteness via Random Submatrices
Ainesh Bakshi, Nadiia Chepurko, Rajesh Jayaram
We study the problem of testing whether a matrix with bounded entries () is positive semi-definite (PSD), or…
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…
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…
Polynomial Time Algorithm for -Stable Clustering Instances
Ainesh Bakshi, Nadiia Chepurko
Clustering with most objective functions is NP-Hard, even to approximate well in the worst case. Recently, there has been work on exploring different notions of stability which len…