102 citations · 786 across the 51 of their papers we have counts for
10 papers · 1 filter
Sketching Transformed Matrices with Applications to Natural Language Processing
Yingyu Liang, Zhao Song, Mengdi Wang +2
Suppose we are given a large matrix that cannot be stored in memory but is in a disk or is presented in a data stream. However, we need to compute a matrix decomposit…
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…
The One-Way Communication Complexity of Dynamic Time Warping Distance
Vladimir Braverman, Moses Charikar, William Kuszmaul +2
We resolve the randomized one-way communication complexity of Dynamic Time Warping (DTW) distance. We show that there is an efficient one-way communication protocol using $\widetil…
Universal Streaming of Subset Norms
Vladimir Braverman, Robert Krauthgamer, Lin F. Yang
Most known algorithms in the streaming model of computation aim to approximate a single function such as an -norm. In 2009, Nelson [\url{https://sublinear.info}, Open Probl…
Revisiting Frequency Moment Estimation in Random Order Streams
Vladimir Braverman, Emanuele Viola, David Woodruff +1
We revisit one of the classic problems in the data stream literature, namely, that of estimating the frequency moments for of an underlying -dimensional vector…
Nearly Optimal Dynamic -Means Clustering for High-Dimensional Data
Wei Hu, Zhao Song, Lin F. Yang +1
We consider the -means clustering problem in the dynamic streaming setting, where points from a discrete Euclidean space can be dynamically inserted to o…
Clustering High Dimensional Dynamic Data Streams
Vladimir Braverman, Gereon Frahling, Harry Lang +2
We present data streaming algorithms for the -median problem in high-dimensional dynamic geometric data streams, i.e. streams allowing both insertions and deletions of points fr…
Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order
Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer +3
A central problem in data streams is to characterize which functions of an underlying frequency vector can be approximated efficiently. Recently there has been considerable effort…
Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors
Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff +1
A central problem in the theory of algorithms for data streams is to determine which functions on a stream can be approximated in sublinear, and especially sub-polynomial or poly-l…
Streaming Symmetric Norms via Measure Concentration
Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut +2
We characterize the streaming space complexity of every symmetric norm (a norm on invariant under sign-flips and coordinate-permutations), by relating this space…