
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes
We introduce a new scalable approximation for Gaussian processes with pr...
read it

Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
We introduce difference estimators for data stream computation, which pr...
read it

ReducedRank Regression with Operator Norm Error
A common data analysis task is the reducedrank regression problem: ...
read it

QuantumInspired Algorithms from Randomized Numerical Linear Algebra
We create classical (nonquantum) dynamic data structures supporting que...
read it

Hutch++: Optimal Stochastic Trace Estimation
We study the problem of estimating the trace of a matrix A that can only...
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...
read it

On Learned Sketches for Randomized Numerical Linear Algebra
We study "learningbased" sketching approaches for diverse tasks in nume...
read it

WOR and p's: Sketches for ℓ_pSampling Without Replacement
Weighted sampling is a fundamental tool in data analysis and machine lea...
read it

Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling
To accelerate kernel methods, we propose a near input sparsity time algo...
read it

Streaming Complexity of SVMs
We study the space complexity of solving the biasregularized SVM proble...
read it

VectorMatrixVector Queries for Solving Linear Algebra, Statistics, and Graph Problems
We consider the general problem of learning about a matrix through vecto...
read it

Approximation Algorithms for Sparse Principal Component Analysis
We present three provably accurate, polynomial time, approximation algor...
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...
read it

NonAdaptive Adaptive Sampling on Turnstile Streams
Adaptive sampling is a useful algorithmic tool for data summarization pr...
read it

Average Case Column Subset Selection for Entrywise ℓ_1Norm Loss
We study the column subset selection problem with respect to the entrywi...
read it

A Framework for Adversarially Robust Streaming Algorithms
We investigate the adversarial robustness of streaming algorithms. In th...
read it

LSFJoin: Locality Sensitive Filtering for Distributed AllPairs Set Similarity Under Skew
Allpairs set similarity is a widely used data mining task, even for lar...
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...
read it

Strong Coresets for Subspace Approximation and kMedian in Nearly Linear Time
Recently the first (1+ϵ)approximate strong coresets for kmedian and su...
read it

Sublinear Time Numerical Linear Algebra for Structured Matrices
We show how to solve a number of problems in numerical linear algebra, s...
read it

Robust and Sample Optimal Algorithms for PSD LowRank Approximation
Recently, Musco and Woodruff (FOCS, 2017) showed that given an n × n pos...
read it

Pseudodeterministic Streaming
A pseudodeterministic algorithm is a (randomized) algorithm which, when...
read it

Graph Spanners in the MessagePassing Model
Graph spanners are sparse subgraphs which approximately preserve all pai...
read it

Optimal Sketching for Kronecker Product Regression and Low Rank Approximation
We study the Kronecker product regression problem, in which the design m...
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 ...
read it

The Query Complexity of Mastermind with ℓ_p Distances
Consider a variant of the Mastermind game in which queries are ℓ_p dista...
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...
read it

The Communication Complexity of Optimization
We consider the communication complexity of a number of distributed opti...
read it

Querying a Matrix through MatrixVector Products
We consider algorithms with access to an unknown matrix M∈F^n × d via ma...
read it

Separating kPlayer from tPlayer OneWay Communication, with Applications to Data Streams
In a kparty communication problem, the k players with inputs x_1, x_2, ...
read it

Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel kmeans Clustering
We present tight lower bounds on the number of kernel evaluations requir...
read it

Dimensionality Reduction for Tukey Regression
We give the first dimensionality reduction methods for the overconstrain...
read it

LowRank Approximation from Communication Complexity
In lowrank approximation with missing entries, given A∈R^n× n and binar...
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)...
read it

Weighted Reservoir Sampling from Distributed Streams
We consider messageefficient continuous random sampling from a distribu...
read it

Optimal Random Sampling from Distributed Streams Revisited
We give an improved algorithm for drawing a random sample from a large d...
read it

The OneWay Communication Complexity of Dynamic Time Warping Distance
We resolve the randomized oneway communication complexity of Dynamic Ti...
read it

Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams
We study the Maximum Independent Set problem for geometric objects given...
read it

Learning Two Layer Rectified Neural Networks in Polynomial Time
Consider the following fundamental learning problem: given input example...
read it

Towards a ZeroOne Law for Entrywise Low Rank Approximation
There are a number of approximation algorithms for NPhard versions of l...
read it

Testing Matrix Rank, Optimally
We show that for the problem of testing if a matrix A ∈ F^n × n has rank...
read it

Sublinear Time LowRank Approximation of Distance Matrices
Let P={ p_1, p_2, ... p_n } and Q = { q_1, q_2 ... q_m } be two point se...
read it

Strong Coresets for kMedian and Subspace Approximation: Goodbye Dimension
We obtain the first strong coresets for the kmedian and subspace approx...
read it

Perfect L_p Sampling in a Data Stream
In this paper, we resolve the onepass space complexity of L_p sampling ...
read it

A PTAS for ℓ_pLow Rank Approximation
A number of recent works have studied algorithms for entrywise ℓ_plow r...
read it

Leveraging WellConditioned Bases: Streaming & Distributed Summaries in Minkowski pNorms
Work on approximate linear algebra has led to efficient distributed and ...
read it

Distributed Statistical Estimation of Matrix Products with Applications
We consider statistical estimations of a matrix product over the integer...
read it

On Sketching the q to p norms
We initiate the study of data dimensionality reduction, or sketching, fo...
read it

High Probability Frequency Moment Sketches
We consider the problem of sketching the pth frequency moment of a vect...
read it

On Coresets for Logistic Regression
Coresets are one of the central methods to facilitate the analysis of la...
read it
David P. Woodruff
is this you? claim profile