
-
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
-
Reduced-Rank Regression with Operator Norm Error
A common data analysis task is the reduced-rank regression problem: ...
read it
-
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
We create classical (non-quantum) 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 "learning-based" sketching approaches for diverse tasks in nume...
read it
-
WOR and p's: Sketches for ℓ_p-Sampling 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 bias-regularized SVM proble...
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...
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
-
Non-Adaptive 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 ℓ_1-Norm 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
-
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...
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 k-Median in Nearly Linear Time
Recently the first (1+ϵ)-approximate strong coresets for k-median 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 Low-Rank Approximation
Recently, Musco and Woodruff (FOCS, 2017) showed that given an n × n pos...
read it
-
Pseudo-deterministic Streaming
A pseudo-deterministic algorithm is a (randomized) algorithm which, when...
read it
-
Graph Spanners in the Message-Passing 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 Matrix-Vector Products
We consider algorithms with access to an unknown matrix M∈F^n × d via ma...
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, ...
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...
read it
-
Dimensionality Reduction for Tukey Regression
We give the first dimensionality reduction methods for the overconstrain...
read it
-
Low-Rank Approximation from Communication Complexity
In low-rank 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 message-efficient 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 One-Way Communication Complexity of Dynamic Time Warping Distance
We resolve the randomized one-way 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 Zero-One Law for Entrywise Low Rank Approximation
There are a number of approximation algorithms for NP-hard 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 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...
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...
read it
-
Perfect L_p Sampling in a Data Stream
In this paper, we resolve the one-pass space complexity of L_p sampling ...
read it
-
A PTAS for ℓ_p-Low Rank Approximation
A number of recent works have studied algorithms for entrywise ℓ_p-low r...
read it
-
Leveraging Well-Conditioned Bases: Streaming & Distributed Summaries in Minkowski p-Norms
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 p-th 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