research
∙
08/01/2023
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree
We study the classic Euclidean Minimum Spanning Tree (MST) problem in th...
share
research
∙
07/24/2023
A faster and simpler algorithm for learning shallow networks
We revisit the well-studied problem of learning a linear combination of ...
research
∙
07/18/2023
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
We consider the question of Gaussian mean testing, a fundamental task in...
research
∙
07/10/2023
Improved Diversity Maximization Algorithms for Matching and Pseudoforest
In this work we consider the diversity maximization problem, where given...
research
∙
06/20/2023
Data Structures for Density Estimation
We study statistical/computational tradeoffs for the following density e...
research
∙
04/15/2023
Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees
An ε-approximate quantile sketch over a stream of n inputs approximates ...
research
∙
04/06/2023
Krylov Methods are (nearly) Optimal for Low-Rank Approximation
We consider the problem of rank-1 low-rank approximation (LRA) in the ma...
research
∙
04/05/2023
Query lower bounds for log-concave sampling
Log-concave sampling has witnessed remarkable algorithmic advances in re...
research
∙
12/09/2022
Robustness Implies Privacy in Statistical Estimation
We study the relationship between adversarial robustness and differentia...
research
∙
11/21/2022
Estimating the Effective Support Size in Constant Query Complexity
Estimating the support size of a distribution is a well-studied problem ...
research
∙
11/09/2022
Sampling an Edge in Sublinear Time Exactly and Optimally
Sampling edges from a graph in sublinear time is a fundamental problem a...
research
∙
11/06/2022
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
Recent work shows that the expressive power of Graph Neural Networks (GN...
research
∙
08/02/2022
Bias Reduction for Sum Estimation
In classical statistics and distribution testing, it is often assumed th...
research
∙
05/03/2022
Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game
The p-processor cup game is a classic and widely studied scheduling prob...
research
∙
04/11/2022
Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets
Motivated by data analysis and machine learning applications, we conside...
research
∙
04/05/2022
All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights
We revisit the problem of privately releasing the all-pairs shortest pat...
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/03/2022
Private High-Dimensional Hypothesis Testing
We provide improved differentially private algorithms for identity testi...
research
∙
11/14/2021
Stochastic and Worst-Case Generalized Sorting Revisited
The generalized sorting problem is a restricted version of standard comp...
research
∙
11/06/2021
Frequency Estimation with One-Sided Error
Frequency estimation is one of the most fundamental problems in streamin...
research
∙
10/22/2021
Tight and Robust Private Mean Estimation with Few Users
In this work, we study high-dimensional mean estimation under user-level...
research
∙
07/05/2021
Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering
Random dimensionality reduction is a versatile tool for speeding up algo...
research
∙
07/01/2021
Almost Tight Approximation Algorithms for Explainable Clustering
Recently, due to an increasing interest for transparency in artificial i...
research
∙
06/15/2021
Learning-based Support Estimation in Sublinear Time
We consider the problem of estimating the number of distinct elements in...
research
∙
11/23/2020
Functions that Preserve Manhattan Distances
What functions, when applied to the pairwise Manhattan distances between...
research
∙
09/02/2020
Circular Trace Reconstruction
Trace Reconstruction is the problem of learning an unknown string x from...
research
∙
07/20/2020
Tolerant Distribution Testing in the Conditional Sampling Model
Recently, there has been significant work studying distribution testing ...
research
∙
04/14/2020
Population Recovery from the Deletion Channel: Nearly Matching Trace Reconstruction Bounds
The population recovery problem asks one to recover an unknown distribut...
research
∙
09/10/2019
Bounds on expected propagation time of probabilistic zero forcing
Probabilistic zero forcing is a coloring game played on a graph where th...
research
∙
10/22/2018
Optimal terminal dimensionality reduction in Euclidean space
Let ε∈(0,1) and X⊂ R^d be arbitrary with |X| having size n>1. The Johnso...
research
∙
07/13/2018
Pairwise Independent Random Walks can be Slightly Unbounded
A family of problems that have been studied in the context of various st...
research
∙
06/19/2018