4 citations · 18 across the 38 of their papers we have counts for
5 papers · 1 filter
Learning-Augmented -means Clustering
Jon C. Ergun, Zhili Feng, Sandeep Silwal +2
-means clustering is a well-studied problem due to its wide applicability. Unfortunately, there exist strong theoretical limits on the performance of any algorithm for the -m…
Truly Perfect Samplers for Data Streams and Sliding Windows
Rajesh Jayaram, David P. Woodruff, Samson Zhou
In the -sampling problem, the goal is to output an index of a vector , such that for all coordinates , \[\textbf{Pr}[i=j] = (1 \pm ε) \frac{G(f…
Noisy Boolean Hidden Matching with Applications
Michael Kapralov, Amulya Musipatla, Jakab Tardos +2
The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper of Gavinsky et. al. [STOC'07], has played an important role in the streaming lower bounds for graph problem…
Learning a Latent Simplex in Input-Sparsity Time
Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan +2
We consider the problem of learning a latent -vertex simplex , given access to , which can be viewed as a data matrix with …
Separations for Estimating Large Frequency Moments on Data Streams
David P. Woodruff, Samson Zhou
We study the classical problem of moment estimation of an underlying vector whose coordinates are implicitly defined through a series of updates in a data stream. We show that…