David P. Woodruff

Learning-Augmented Sketches for Hessians

Sketching is a dimensionality reduction technique where one compresses a...
02/24/2021 ∙ by Yi Li, et al. ∙ 0 ∙ share

read it
Subspace exploration: Bounds on Projected Frequency Estimation

Given an n × d dimensional dataset A, a projection query specifies a sub...
01/19/2021 ∙ by Graham Cormode, et al. ∙ 0 ∙ share

read it
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes

We introduce a new scalable approximation for Gaussian processes with pr...
11/17/2020 ∙ by Quang Minh Hoang, et al. ∙ 0 ∙ share

read it
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators

We introduce difference estimators for data stream computation, which pr...
11/15/2020 ∙ by David P. Woodruff, et al. ∙ 0 ∙ share

read it
Reduced-Rank Regression with Operator Norm Error

A common data analysis task is the reduced-rank regression problem: ...
11/09/2020 ∙ by Praneeth Kacham, et al. ∙ 0 ∙ share

read it
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra

We create classical (non-quantum) dynamic data structures supporting que...
11/09/2020 ∙ by Nadiia Chepurko, et al. ∙ 13 ∙ share

read it
Hutch++: Optimal Stochastic Trace Estimation

We study the problem of estimating the trace of a matrix A that can only...
10/19/2020 ∙ by Raphael A. Meyer, et al. ∙ 0 ∙ share

read it
Optimal ℓ_1 Column Subset Selection and a Fast PTAS for Low Rank Approximation

We study the problem of entrywise ℓ_1 low rank approximation. We give th...
07/20/2020 ∙ by Arvind V. Mahankali, et al. ∙ 0 ∙ share

read it
On Learned Sketches for Randomized Numerical Linear Algebra

We study "learning-based" sketching approaches for diverse tasks in nume...
07/20/2020 ∙ by Simin Liu, et al. ∙ 20 ∙ share

read it
WOR and p's: Sketches for ℓ_p-Sampling Without Replacement

Weighted sampling is a fundamental tool in data analysis and machine lea...
07/14/2020 ∙ by Edith Cohen, et al. ∙ 2 ∙ share

read it
Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling

To accelerate kernel methods, we propose a near input sparsity time algo...
07/08/2020 ∙ by David P. Woodruff, et al. ∙ 0 ∙ share

read it
Streaming Complexity of SVMs

We study the space complexity of solving the bias-regularized SVM proble...
07/07/2020 ∙ by Alexandr Andoni, et al. ∙ 0 ∙ share

read it
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems

We consider the general problem of learning about a matrix through vecto...
06/24/2020 ∙ by Cyrus Rashtchian, et al. ∙ 0 ∙ share

read it
Approximation Algorithms for Sparse Principal Component Analysis

We present three provably accurate, polynomial time, approximation algor...
06/23/2020 ∙ by Agniva Chowdhury, et al. ∙ 0 ∙ share

read it
How to reduce dimension with PCA and random projections?

In our "big data" age, the size and complexity of data is steadily incre...
05/01/2020 ∙ by Fan Yang, et al. ∙ 0 ∙ share

read it
Non-Adaptive Adaptive Sampling on Turnstile Streams

Adaptive sampling is a useful algorithmic tool for data summarization pr...
04/23/2020 ∙ by Sepideh Mahabadi, et al. ∙ 0 ∙ share

read it
Average Case Column Subset Selection for Entrywise ℓ_1-Norm Loss

We study the column subset selection problem with respect to the entrywi...
04/16/2020 ∙ by Zhao Song, et al. ∙ 0 ∙ share

read it
A Framework for Adversarially Robust Streaming Algorithms

We investigate the adversarial robustness of streaming algorithms. In th...
03/31/2020 ∙ by Omri Ben-Eliezer, et al. ∙ 0 ∙ share

read it
LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew

All-pairs set similarity is a widely used data mining task, even for lar...
03/06/2020 ∙ by Cyrus Rashtchian, et al. ∙ 0 ∙ share

read it
Span Recovery for Deep Neural Networks with Applications to Input Obfuscation

The tremendous success of deep neural networks has motivated the need to...
02/19/2020 ∙ by Rajesh Jayaram, et al. ∙ 0 ∙ share

read it
Strong Coresets for Subspace Approximation and k-Median in Nearly Linear Time

Recently the first (1+ϵ)-approximate strong coresets for k-median and su...
12/27/2019 ∙ by Zhili Feng, et al. ∙ 0 ∙ share

read it
Sublinear Time Numerical Linear Algebra for Structured Matrices

We show how to solve a number of problems in numerical linear algebra, s...
12/12/2019 ∙ by Xiaofei Shi, et al. ∙ 0 ∙ share

read it
Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation

Recently, Musco and Woodruff (FOCS, 2017) showed that given an n × n pos...
12/09/2019 ∙ by Ainesh Bakshi, et al. ∙ 0 ∙ share

read it
Pseudo-deterministic Streaming

A pseudo-deterministic algorithm is a (randomized) algorithm which, when...
11/26/2019 ∙ by Shafi Goldwasser, et al. ∙ 0 ∙ share

read it
Graph Spanners in the Message-Passing Model

Graph spanners are sparse subgraphs which approximately preserve all pai...
11/14/2019 ∙ by Manuel Fernandez, et al. ∙ 0 ∙ share

read it
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation

We study the Kronecker product regression problem, in which the design m...
09/29/2019 ∙ by Huaian Diao, et al. ∙ 8 ∙ share

read it
Total Least Squares Regression in Input Sparsity Time

In the total least squares problem, one is given an m × n matrix A, and ...
09/27/2019 ∙ by Huaian Diao, et al. ∙ 0 ∙ share

read it
The Query Complexity of Mastermind with ℓ_p Distances

Consider a variant of the Mastermind game in which queries are ℓ_p dista...
09/24/2019 ∙ by Manuel Fernandez, et al. ∙ 0 ∙ share

read it
Towards Optimal Moment Estimation in Streaming and Distributed Models

One of the oldest problems in the data stream model is to approximate th...
07/12/2019 ∙ by Rajesh Jayaram, et al. ∙ 0 ∙ share

read it
The Communication Complexity of Optimization

We consider the communication complexity of a number of distributed opti...
06/13/2019 ∙ by Santosh S. Vempala, et al. ∙ 0 ∙ share

read it
Querying a Matrix through Matrix-Vector Products

We consider algorithms with access to an unknown matrix M∈F^n × d via ma...
06/13/2019 ∙ by Xiaoming Sun, et al. ∙ 0 ∙ share

read it
Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams

In a k-party communication problem, the k players with inputs x_1, x_2, ...
05/17/2019 ∙ by David P. Woodruff, et al. ∙ 0 ∙ share

read it
Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel k-means Clustering

We present tight lower bounds on the number of kernel evaluations requir...
05/15/2019 ∙ by Manuel Fernandez, et al. ∙ 0 ∙ share

read it
Dimensionality Reduction for Tukey Regression

We give the first dimensionality reduction methods for the overconstrain...
05/14/2019 ∙ by Kenneth L. Clarkson, et al. ∙ 0 ∙ share

read it
Low-Rank Approximation from Communication Complexity

In low-rank approximation with missing entries, given A∈R^n× n and binar...
04/22/2019 ∙ by Cameron Musco, et al. ∙ 0 ∙ share

read it
Tight Bounds for the Subspace Sketch Problem with Applications

In the subspace sketch problem one is given an n× d matrix A with O((nd)...
04/11/2019 ∙ by Yi Li, et al. ∙ 0 ∙ share

read it
Weighted Reservoir Sampling from Distributed Streams

We consider message-efficient continuous random sampling from a distribu...
04/08/2019 ∙ by Rajesh Jayaram, et al. ∙ 0 ∙ share

read it
Optimal Random Sampling from Distributed Streams Revisited

We give an improved algorithm for drawing a random sample from a large d...
03/28/2019 ∙ by Srikanta Tirthapura, et al. ∙ 0 ∙ share

read it
The One-Way Communication Complexity of Dynamic Time Warping Distance

We resolve the randomized one-way communication complexity of Dynamic Ti...
03/08/2019 ∙ by Vladimir Braverman, et al. ∙ 0 ∙ share

read it
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams

We study the Maximum Independent Set problem for geometric objects given...
02/27/2019 ∙ by Ainesh Bakshi, et al. ∙ 0 ∙ share

read it
Learning Two Layer Rectified Neural Networks in Polynomial Time

Consider the following fundamental learning problem: given input example...
11/05/2018 ∙ by Ainesh Bakshi, et al. ∙ 0 ∙ share

read it
Towards a Zero-One Law for Entrywise Low Rank Approximation

There are a number of approximation algorithms for NP-hard versions of l...
11/04/2018 ∙ by Zhao Song, et al. ∙ 0 ∙ share

read it
Testing Matrix Rank, Optimally

We show that for the problem of testing if a matrix A ∈ F^n × n has rank...
10/18/2018 ∙ by Maria-Florina Balcan, et al. ∙ 0 ∙ share

read it
Sublinear Time Low-Rank Approximation of Distance Matrices

Let P={ p_1, p_2, ... p_n } and Q = { q_1, q_2 ... q_m } be two point se...
09/19/2018 ∙ by Ainesh Bakshi, et al. ∙ 0 ∙ share

read it
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension

We obtain the first strong coresets for the k-median and subspace approx...
09/09/2018 ∙ by Christian Sohler, et al. ∙ 0 ∙ share

read it
Perfect L_p Sampling in a Data Stream

In this paper, we resolve the one-pass space complexity of L_p sampling ...
08/16/2018 ∙ by Rajesh Jayaram, et al. ∙ 0 ∙ share

read it
A PTAS for ℓ_p-Low Rank Approximation

A number of recent works have studied algorithms for entrywise ℓ_p-low r...
07/16/2018 ∙ by Frank Ban, et al. ∙ 0 ∙ share

read it
Leveraging Well-Conditioned Bases: Streaming & Distributed Summaries in Minkowski p-Norms

Work on approximate linear algebra has led to efficient distributed and ...
07/06/2018 ∙ by Graham Cormode, et al. ∙ 0 ∙ share

read it
Distributed Statistical Estimation of Matrix Products with Applications

We consider statistical estimations of a matrix product over the integer...
07/02/2018 ∙ by David P. Woodruff, et al. ∙ 0 ∙ share

read it
On Sketching the q to p norms

We initiate the study of data dimensionality reduction, or sketching, fo...
06/17/2018 ∙ by Aditya Krishnan, et al. ∙ 0 ∙ share

read it

David P. Woodruff

Featured Co-authors