research
∙
07/09/2023
Private Data Stream Analysis for Universal Symmetric Norm Estimation
We study how to release summary statistics on a data stream subject to t...
share
research
∙
06/02/2023
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization
We introduce efficient (1+ε)-approximation algorithms for the binary mat...
research
∙
04/14/2023
Robust Algorithms on Adaptive Inputs from Bounded Adversaries
We study dynamic algorithms robust to adaptive input generated from sour...
research
∙
03/09/2023
Provable Data Subset Selection For Efficient Neural Network Training
Radial basis function neural networks (RBFNN) are well-known for their c...
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/22/2023
Selective experience replay compression using coresets for lifelong deep reinforcement learning in medical imaging
Selective experience replay is a popular strategy for integrating lifelo...
research
∙
02/22/2023
Differentially Private L_2-Heavy Hitters in the Sliding Window Model
The data management of large companies often prioritize more recent data...
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
∙
12/01/2022
Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation
Kernel matrices, as well as weighted graphs represented by them, are ubi...
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/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
∙
10/07/2022
How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
We develop a framework for efficiently transforming certain approximatio...
research
∙
09/21/2022
Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
Semidefinite programming (SDP) is a unifying framework that generalizes ...
research
∙
07/16/2022
Adaptive Sketches for Robust Regression with Importance Sampling
We introduce data structures for solving robust regression through stoch...
research
∙
06/29/2022
Hardness and Algorithms for Robust and Sparse Optimization
We explore algorithms and limitations for sparse optimization problems s...
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
∙
03/14/2022
Fast Regression for Structured Inputs
We study the ℓ_p regression problem, which requires finding 𝐱∈ℝ^d that m...
research
∙
03/08/2022
New Coresets for Projective Clustering and Applications
(j,k)-projective clustering is the natural generalization of the family ...
research
∙
10/27/2021
Learning-Augmented k-means Clustering
k-means clustering is a well-studied problem due to its wide applicabili...
research
∙
10/18/2021
Dimensionality Reduction for Wasserstein Barycenter
The Wasserstein barycenter is a geometric construct which captures the n...
research
∙
09/03/2021
Symmetric Norm Estimation and Regression on Sliding Windows
The sliding window model generalizes the standard streaming model and of...
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
∙
07/06/2021
Noisy Boolean Hidden Matching with Applications
The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper...
research
∙
06/28/2021
Adversarial Robustness of Streaming Algorithms through Importance Sampling
In this paper, we introduce adversarially robust streaming algorithms fo...
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...
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
∙
09/09/2020
Sensitivity Analysis of the Maximum Matching Problem
We consider the sensitivity of algorithms for the maximum matching probl...
research
∙
08/19/2020
Data-Independent Structured Pruning of Neural Networks via Coresets
Model compression is crucial for deployment of neural networks on device...
research
∙
06/23/2020
Approximation Algorithms for Sparse Principal Component Analysis
We present three provably accurate, polynomial time, approximation algor...
research
∙
06/19/2020
On the Security of Proofs of Sequential Work in a Post-Quantum World
A proof of sequential work allows a prover to convince a resource-bounde...
research
∙
06/09/2020
On the Economics of Offline Password Cracking
We develop an economic model of an offline password cracker which allows...
research
∙
04/23/2020
Non-Adaptive Adaptive Sampling on Turnstile Streams
Adaptive sampling is a useful algorithmic tool for data summarization pr...
research
∙
11/16/2019
Memory-Efficient Performance Monitoring on Programmable Switches with Lean Algorithms
Network performance problems are notoriously difficult to diagnose. Prio...
research
∙
11/15/2019
Computationally Data-Independent Memory Hard Functions
Memory hard functions (MHFs) are an important cryptographic primitive th...
research
∙
10/13/2019
Fast Fourier Sparsity Testing
A function f : F_2^n →R is s-sparse if it has at most s non-zero Fourier...
research
∙
10/12/2019
"Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack
The problem of selecting a small-size representative summary of a large ...
research
∙
09/25/2019
On Locally Decodable Codes in Resource Bounded Channels
Constructions of locally decodable codes (LDCs) have one of two undesira...
research
∙
07/17/2019
Improved Algorithms for Time Decay Streams
In the time-decay model for data streams, elements of an underlying data...
research
∙
07/09/2019
On Activation Function Coresets for Network Pruning
Model compression provides a means to efficiently deploy deep neural net...
research
∙
07/01/2019
Approximate F_2-Sketching of Valuation Functions
We study the problem of constructing a linear sketch of minimum dimensio...
research
∙
05/07/2019
Adversarially Robust Submodular Maximization under Knapsack Constraints
We propose the first adversarially robust algorithm for monotone submodu...
research
∙
04/17/2019
Approximating Cumulative Pebbling Cost is Unique Games Hard
The cumulative pebbling complexity of a directed acyclic graph G is defi...
research
∙
05/10/2018
Numerical Linear Algebra in the Sliding Window Model
We initiate the study of numerical linear algebra in the sliding window ...
research
∙
05/01/2018
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
We study the distinct elements and ℓ_p-heavy hitters problems in the sli...
research
∙
03/15/2018
Relaxed Locally Correctable Codes in Computationally Bounded Channels
Error-correcting codes that admit local decoding and correcting algorith...
research
∙
02/20/2018
Periodicity in Data Streams with Wildcards
We investigate the problem of detecting periodic trends within a string ...
research
∙
11/12/2017
Longest Alignment with Edits in Data Streams
Analyzing patterns in data streams generated by network traffic, sensor ...
research
∙
11/02/2017