1 citations · 1 across the 14 of their papers we have counts for
10 papers · 1 filter
High Probability Streaming Lower Bounds for Estimation
William Swartworth, David P. Woodruff, Samson Zhou
Estimating the second frequency moment () of an underlying frequency vector is a fundamental problem in the streaming model. While recent work by Braverman and Zamir [STOC 202…
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),…
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…
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,…
Fast Sampling Based Sketches for Tensors
William Swartworth, David P. Woodruff
We introduce a new approach for applying sampling-based sketches to two and three mode tensors. We illustrate our technique to construct sketches for the classical problems of $\el…
Improving the Bit Complexity of Communication for Distributed Convex Optimization
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan +3
We consider the communication complexity of some fundamental convex optimization problems in the point-to-point (coordinator) and blackboard communication models. We strengthen kno…
Optimal Eigenvalue Approximation via Sketching
William Swartworth, David P. Woodruff
Given a symmetric matrix , we show from the simple sketch , where is a Gaussian matrix with rows, that there is a procedure for approximating all eigen…
Testing Positive Semidefiniteness Using Linear Measurements
Deanna Needell, William Swartworth, David P. Woodruff
We study the problem of testing whether a symmetric input matrix is symmetric positive semidefinite (PSD), or is -far from the PSD cone, meaning that $λ_{\min}(…