5 papers
Unbiased Insights: Optimal Streaming Algorithms for Sampling, the Forget Model, and Beyond
Honghao Lin, Hoai-An Nguyen, William Swartworth +1
We study sampling and frequency moment estimation in a single-pass insertion-only data stream. For , we present a nearly space-optimal approximate sa…
Perfect Sampling with Polylogarithmic Update Time
William Swartworth, David P. Woodruff, Samson Zhou
Perfect sampling in a stream was introduced by Jayaram and Woodruff (FOCS 2018) as a streaming primitive which, given turnstile updates to a vector $x \in \{-\text{poly}(n),…
Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model
Shiyuan Feng, William Swartworth, David P. Woodruff
We consider the heavy-hitters and moment estimation problems in the sliding window model. For moment estimation with , we show that it is possible to give a…
Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
Raphael A. Meyer, William Swartworth, David P. Woodruff
We study the computational model where we can access a matrix only by computing matrix-vector products for vectors of the form $\mathrm{x} = \ma…
Tight Sampling Bounds for Eigenvalue Approximation
William Swartworth, David P. Woodruff
We consider the problem of estimating the spectrum of a symmetric bounded entry (not necessarily PSD) matrix via entrywise sampling. This problem was introduced by [Bhattacharjee,…