research
∙
07/11/2023
ℓ_p-Regression in the Arbitrary Partition Model of Communication
We consider the randomized communication complexity of the distributed ℓ...
share
research
∙
06/02/2023
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization
We introduce efficient (1+ε)-approximation algorithms for the binary mat...
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...
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...
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...
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...
research
∙
09/30/2022
Optimal Query Complexities for Dynamic Trace Estimation
We consider the problem of minimizing the number of matrix-vector querie...
research
∙
07/17/2022
Online Lewis Weight Sampling
The seminal work of Cohen and Peng introduced Lewis weight sampling to t...
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...
research
∙
04/13/2022
Sketching Algorithms and Lower Bounds for Ridge Regression
We give a sketching-based iterative algorithm that computes 1+ε approxim...
research
∙
11/09/2021
Active Sampling for Linear Regression Beyond the ℓ_2 Norm
We study active sampling algorithms for linear regression, which aim to ...
research
∙
07/16/2021
Single Pass Entrywise-Transformed Low Rank Approximation
In applications such as natural language processing or computer vision, ...
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 ...
research
∙
05/08/2021
Separations for Estimating Large Frequency Moments on Data Streams
We study the classical problem of moment estimation of an underlying vec...
research
∙
11/15/2020
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
We introduce difference estimators for data stream computation, which pr...
research
∙
11/09/2020
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
We create classical (non-quantum) dynamic data structures supporting que...
research
∙
12/09/2019
Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation
Recently, Musco and Woodruff (FOCS, 2017) showed that given an n × n pos...
research
∙
04/25/2018
Improved Algorithms for Adaptive Compressed Sensing
In the problem of adaptive compressed sensing, one wants to estimate an ...
research
∙
03/23/2018
Data Streams with Bounded Deletions
Two prevalent models in the data stream literature are the insertion-onl...
research
∙
01/13/2018
Tight Bounds for ℓ_p Oblivious Subspace Embeddings
An ℓ_p oblivious subspace embedding is a distribution over r × n matrice...
research
∙
12/27/2017
