921 citations · 1.4k across the 54 of their papers we have counts for
6 papers · 1 filter
Recovery from Non-Decomposable Distance Oracles
Zhuangfei Hu, Xinda Li, David P. Woodruff +2
A line of work has looked at the problem of recovering an input from distance queries. In this setting, there is an unknown sequence , and one chooses a set…
Efficient Symmetric Norm Regression via Linear Sketching
Zhao Song, Ruosong Wang, Lin F. Yang +2
We provide efficient algorithms for overconstrained linear regression problems with size when the loss function is a symmetric norm (a norm invariant under sign-flips…
Testing Matrix Rank, Optimally
Maria-Florina Balcan, Yi Li, David P. Woodruff +1
We show that for the problem of testing if a matrix has rank at most , or requires changing an -fraction of entries to have rank at most , there is…
Improved Algorithms for Adaptive Compressed Sensing
Vasileios Nakos, Xiaofei Shi, David P. Woodruff +1
In the problem of adaptive compressed sensing, one wants to estimate an approximately -sparse vector from linear measurements …
Matrix Completion and Related Problems via Strong Duality
Maria-Florina Balcan, Yingyu Liang, David P. Woodruff +1
This work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and its dual have the same optimum. Thi…
Approximate Personalized PageRank on Dynamic Graphs
Hongyang Zhang, Peter Lofgren, Ashish Goel
We propose and analyze two algorithms for maintaining approximate Personalized PageRank (PPR) vectors on a dynamic graph, where edges are added or deleted. Our algorithms are natur…