David P. Woodruff

activity

20242026

collaborators

Showing 2025Show all

4 papers · 1 filter

cs.DS2025

Perfect $L_{p}$ Sampling with Polylogarithmic Update Time

William Swartworth, David P. Woodruff, Samson Zhou

Perfect $L_{p}$ 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),…

cs.DS2025

Unbiased Insights: Optimal Streaming Algorithms for $ℓ_{p}$ Sampling, the Forget Model, and Beyond

Honghao Lin, Hoai-An Nguyen, William Swartworth +1

We study $ℓ_{p}$ sampling and frequency moment estimation in a single-pass insertion-only data stream. For $p \in (0, 2)$ , we present a nearly space-optimal approximate $ℓ_{p}$ sa…

cs.DS2025

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 $F_{p}$ moment estimation problems in the sliding window model. For $F_{p}$ moment estimation with $1 < p \leq 2$ , we show that it is possible to give a…

cs.DS2025

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 $A$ only by computing matrix-vector products $A x$ for vectors of the form $\mathrm{x} = \ma…

Perfect Lp​ Sampling with Polylogarithmic Update Time

Unbiased Insights: Optimal Streaming Algorithms for ℓp​ Sampling, the Forget Model, and Beyond

Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model

Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra

Perfect $L_{p}$ Sampling with Polylogarithmic Update Time

Unbiased Insights: Optimal Streaming Algorithms for $ℓ_{p}$ Sampling, the Forget Model, and Beyond