research
∙
07/11/2023
ℓ_p-Regression in the Arbitrary Partition Model of Communication
We consider the randomized communication complexity of the distributed ℓ...
share
research
∙
07/07/2023
Improved Algorithms for White-Box Adversarial Streams
We study streaming algorithms in the white-box adversarial stream model,...
research
∙
06/11/2023
Learning the Positions in CountSketch
We consider sketching algorithms which first compress data by multiplica...
research
∙
06/02/2023
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization
We introduce efficient (1+ε)-approximation algorithms for the binary mat...
research
∙
06/01/2023
Sharper Bounds for ℓ_p Sensitivity Sampling
In large scale machine learning, random sampling is a popular way to app...
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/18/2023
Optimal Eigenvalue Approximation via Sketching
Given a symmetric matrix A, we show from the simple sketch GAG^T, where ...
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...
research
∙
04/14/2023
Robust Algorithms on Adaptive Inputs from Bounded Adversaries
We study dynamic algorithms robust to adaptive input generated from sour...
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
∙
04/05/2023
Optimal Sketching Bounds for Sparse Linear Regression
We study oblivious sketching for k-sparse linear regression under variou...
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...
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 ...
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
∙
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:[...
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/17/2022
Streaming Algorithms with Large Approximation Factors
We initiate a broad study of classical problems in the streaming model w...
research
∙
07/16/2022
Adaptive Sketches for Robust Regression with Importance Sampling
We introduce data structures for solving robust regression through stoch...
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
∙
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...
research
∙
06/24/2022
Learning Augmented Binary Search Trees
A treap is a classic randomized binary search tree data structure that i...
research
∙
04/21/2022
Memory Bounds for the Experts Problem
Online learning with expert advice is a fundamental problem of sequentia...
research
∙
04/19/2022
The White-Box Adversarial Data Stream Model
We study streaming algorithms in the white-box adversarial model, where ...
research
∙
04/13/2022
Sketching Algorithms and Lower Bounds for Ridge Regression
We give a sketching-based iterative algorithm that computes 1+ε approxim...
research
∙
04/08/2022
High-Dimensional Geometric Streaming in Polynomial Space
Many existing algorithms for streaming geometric data analysis have been...
research
∙
04/08/2022
Testing Positive Semidefiniteness Using Linear Measurements
We study the problem of testing whether a symmetric d × d input matrix A...
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 ...
research
∙
03/14/2022
Fast Regression for Structured Inputs
We study the ℓ_p regression problem, which requires finding 𝐱∈ℝ^d that m...
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) ...
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...
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...
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
∙
11/06/2021
Frequency Estimation with One-Sided Error
Frequency estimation is one of the most fundamental problems in streamin...
research
∙
11/01/2021
Improved Algorithms for Low Rank Approximation from Sparsity
We overcome two major bottlenecks in the study of low rank approximation...
research
∙
10/27/2021
Learning-Augmented k-means Clustering
k-means clustering is a well-studied problem due to its wide applicabili...
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 ...
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...
research
∙
08/21/2021
Fast Sketching of Polynomial Kernels of Polynomial Degree
Kernel methods are fundamental in machine learning, and faster algorithm...
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...
research
∙
07/16/2021
Single Pass Entrywise-Transformed Low Rank Approximation
In applications such as natural language processing or computer vision, ...
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...
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...
research
∙
07/12/2021
In-Database Regression in Input Sparsity Time
Sketching is a powerful dimensionality reduction technique for accelerat...
research
∙
07/06/2021
Noisy Boolean Hidden Matching with Applications
The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper...
research
∙
07/03/2021
Average-Case Communication Complexity of Statistical Problems
We study statistical problems, such as planted clique, its variants, and...
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...
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/17/2021