David P. Woodruff

research

∙ 07/11/2023

ℓ_p-Regression in the Arbitrary Partition Model of Communication

We consider the randomized communication complexity of the distributed ℓ...

0 Yi Li, et al. ∙

research

∙ 07/07/2023

Improved Algorithms for White-Box Adversarial Streams

We study streaming algorithms in the white-box adversarial stream model,...

0 Ying Feng, et al. ∙

research

∙ 06/11/2023

Learning the Positions in CountSketch

We consider sketching algorithms which first compress data by multiplica...

0 Yi Li, et al. ∙

research

∙ 06/02/2023

Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization

We introduce efficient (1+ε)-approximation algorithms for the binary mat...

0 Ameya Velingker, et al. ∙

research

∙ 06/01/2023

Sharper Bounds for ℓ_p Sensitivity Sampling

In large scale machine learning, random sampling is a popular way to app...

0 David P. Woodruff, et al. ∙

research

∙ 05/10/2023

Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra

Given 𝐀∈ℝ^n × n with entries bounded in magnitude by 1, it is well-known...

0 Rajarshi Bhattacharjee, et al. ∙

research

∙ 04/18/2023

Optimal Eigenvalue Approximation via Sketching

Given a symmetric matrix A, we show from the simple sketch GAG^T, where ...

0 William Swartworth, et al. ∙

research

∙ 04/18/2023

New Subset Selection Algorithms for Low Rank Approximation: Offline and Online

Subset selection for the rank k approximation of an n× d matrix A offers...

0 David P. Woodruff, et al. ∙

research

∙ 04/14/2023

Robust Algorithms on Adaptive Inputs from Bounded Adversaries

We study dynamic algorithms robust to adaptive input generated from sour...

0 Yeshwanth Cherapanamjeri, et al. ∙

research

∙ 04/13/2023

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming

We revisit Nisan's classical pseudorandom generator (PRG) for space-boun...

0 Praneeth Kacham, et al. ∙

research

∙ 04/05/2023

Optimal Sketching Bounds for Sparse Linear Regression

We study oblivious sketching for k-sparse linear regression under variou...

0 Tung Mai, et al. ∙

research

∙ 03/03/2023

Streaming Algorithms for Learning with Experts: Deterministic Versus Robust

In the online learning with experts problem, an algorithm must make a pr...

0 David P. Woodruff, et al. ∙

research

∙ 02/11/2023

On Differential Privacy and Adaptive Data Analysis with Bounded Space

We study the space complexity of the two related fields of differential ...

0 Itai Dinur, et al. ∙

research

∙ 11/18/2022

Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time

We study fundamental problems in linear algebra, such as finding a maxim...

0 Yeshwanth Cherapanamjeri, et al. ∙

research

∙ 11/14/2022

The ℓ_p-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines

In the ℓ_p-subspace sketch problem, we are given an n× d matrix A with n...

0 Yi Li, et al. ∙

research

∙ 11/13/2022

Near-Linear Sample Complexity for L_p Polynomial Regression

We study L_p polynomial regression. Given query access to a function f:[...

0 Raphael A. Meyer, et al. ∙

research

∙ 09/30/2022

Optimal Query Complexities for Dynamic Trace Estimation

We consider the problem of minimizing the number of matrix-vector querie...

0 David P. Woodruff, et al. ∙

research

∙ 07/17/2022

Online Lewis Weight Sampling

The seminal work of Cohen and Peng introduced Lewis weight sampling to t...

0 David P. Woodruff, et al. ∙

research

∙ 07/17/2022

Streaming Algorithms with Large Approximation Factors

We initiate a broad study of classical problems in the streaming model w...

0 Yi Li, et al. ∙

research

∙ 07/16/2022

Adaptive Sketches for Robust Regression with Importance Sampling

We introduce data structures for solving robust regression through stoch...

0 Sepideh Mahabadi, et al. ∙

research

∙ 07/15/2022

Low Rank Approximation for General Tensor Networks

We study the problem of approximating a given tensor with q modes A ∈ℝ^n...

0 Arvind V. Mahankali, et al. ∙

research

∙ 06/26/2022

Bounding the Width of Neural Networks via Coupled Initialization – A Worst Case Analysis

A common method in training neural networks is to initialize all the wei...

0 Alexander Munteanu, et al. ∙

research

∙ 06/24/2022

Learning Augmented Binary Search Trees

A treap is a classic randomized binary search tree data structure that i...

0 Honghao Lin, et al. ∙

research

∙ 04/21/2022

Memory Bounds for the Experts Problem

Online learning with expert advice is a fundamental problem of sequentia...

0 Vaidehi Srinivas, et al. ∙

research

∙ 04/19/2022

The White-Box Adversarial Data Stream Model

We study streaming algorithms in the white-box adversarial model, where ...

0 Miklos Ajtai, et al. ∙

research

∙ 04/13/2022

Sketching Algorithms and Lower Bounds for Ridge Regression

We give a sketching-based iterative algorithm that computes 1+ε approxim...

0 Praneeth Kacham, et al. ∙

research

∙ 04/08/2022

High-Dimensional Geometric Streaming in Polynomial Space

Many existing algorithms for streaming geometric data analysis have been...

0 David P. Woodruff, et al. ∙

research

∙ 04/08/2022

Testing Positive Semidefiniteness Using Linear Measurements

We study the problem of testing whether a symmetric d × d input matrix A...

0 Deanna Needell, et al. ∙

research

∙ 03/17/2022

Triangle and Four Cycle Counting with Predictions in Graph Streams

We propose data-driven one-pass streaming algorithms for estimating the ...

2 Justin Y. Chen, et al. ∙

research

∙ 03/14/2022

Fast Regression for Structured Inputs

We study the ℓ_p regression problem, which requires finding 𝐱∈ℝ^d that m...

0 Raphael A. Meyer, et al. ∙

research

∙ 02/20/2022

Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings

We consider the following oblivious sketching problem: given ϵ∈ (0,1/3) ...

0 Yi Li, et al. ∙

research

∙ 02/10/2022

Low-Rank Approximation with 1/ε^1/3 Matrix-Vector Products

We study iterative methods based on Krylov subspaces for low-rank approx...

4 Ainesh Bakshi, et al. ∙

research

∙ 02/09/2022

Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time

We give an input sparsity time sampling algorithm for spectrally approxi...

0 David P. Woodruff, et al. ∙

research

∙ 11/09/2021

Active Sampling for Linear Regression Beyond the ℓ_2 Norm

We study active sampling algorithms for linear regression, which aim to ...

0 Cameron Musco, et al. ∙

research

∙ 11/06/2021

Frequency Estimation with One-Sided Error

Frequency estimation is one of the most fundamental problems in streamin...

0 Piotr Indyk, et al. ∙

research

∙ 11/01/2021

Improved Algorithms for Low Rank Approximation from Sparsity

We overcome two major bottlenecks in the study of low rank approximation...

0 David P. Woodruff, et al. ∙

research

∙ 10/27/2021

Learning-Augmented k-means Clustering

k-means clustering is a well-studied problem due to its wide applicabili...

0 Jon Ergun, et al. ∙

research

∙ 08/26/2021

Truly Perfect Samplers for Data Streams and Sliding Windows

In the G-sampling problem, the goal is to output an index i of a vector ...

0 Rajesh Jayaram, et al. ∙

research

∙ 08/23/2021

The Product of Gaussian Matrices is Close to Gaussian

We study the distribution of the matrix product G_1 G_2 ⋯ G_r of r indep...

0 Yi Li, et al. ∙

research

∙ 08/21/2021

Fast Sketching of Polynomial Kernels of Polynomial Degree

Kernel methods are fundamental in machine learning, and faster algorithm...

0 Zhao Song, et al. ∙

research

∙ 07/16/2021

Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time

Currently, in the numerical linear algebra community, it is thought that...

24 Nadiia Chepurko, et al. ∙

research

∙ 07/16/2021

Single Pass Entrywise-Transformed Low Rank Approximation

In applications such as natural language processing or computer vision, ...

0 Yifei Jiang, et al. ∙

research

∙ 07/16/2021

Streaming and Distributed Algorithms for Robust Column Subset Selection

We give the first single-pass streaming algorithm for Column Subset Sele...

0 Shuli Jiang, et al. ∙

research

∙ 07/15/2021

An Efficient Semi-Streaming PTAS for Tournament Feedback ArcSet with Few Passes

We present the first semi-streaming PTAS for the minimum feedback arc se...

0 Anubhav Baweja, et al. ∙

research

∙ 07/12/2021

In-Database Regression in Input Sparsity Time

Sketching is a powerful dimensionality reduction technique for accelerat...

0 Rajesh Jayaram, et al. ∙

research

∙ 07/06/2021

Noisy Boolean Hidden Matching with Applications

The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper...

0 Michael Kapralov, et al. ∙

research

∙ 07/03/2021

Average-Case Communication Complexity of Statistical Problems

We study statistical problems, such as planted clique, its variants, and...

0 Cyrus Rashtchian, et al. ∙

research

∙ 06/16/2021

Non-PSD Matrix Sketching with Applications to Regression and Optimization

A variety of dimensionality reduction techniques have been applied for c...

0 Zhili Feng, et al. ∙

research

∙ 05/24/2021

A Simple Proof of a New Set Disjointness with Applications to Data Streams

The multiplayer promise set disjointness is one of the most widely used ...

0 Akshay Kamath, et al. ∙

research

∙ 05/17/2021

Learning a Latent Simplex in Input-Sparsity Time

We consider the problem of learning a latent k-vertex simplex K⊂ℝ^d, giv...

0 Ainesh Bakshi, et al. ∙

David P. Woodruff

Featured Co-authors