research
∙
06/07/2023
Fast Optimal Locally Private Mean Estimation via Random Projections
We study the problem of locally private mean estimation of high-dimensio...
share
research
∙
02/13/2023
Sparse Dimensionality Reduction Revisited
The sparse Johnson-Lindenstrauss transform is one of the central techniq...
research
∙
11/22/2022
Generalized Private Selection and Testing with High Confidence
Composition theorems are general and powerful tools that facilitate priv...
research
∙
11/11/2022
Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
The problem of learning threshold functions is a fundamental one in mach...
research
∙
11/08/2022
On the amortized complexity of approximate counting
Naively storing a counter up to value n would require Ω(log n) bits of m...
research
∙
07/03/2022
Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs
CountSketch and Feature Hashing (the "hashing trick") are popular random...
research
∙
05/19/2022
Estimation of Entropy in Constant Space with Improved Sample Complexity
Recent work of Acharya et al. (NeurIPS 2019) showed how to estimate the ...
research
∙
03/03/2022
Uniform Approximations for Randomized Hadamard Transforms with Applications
Randomized Hadamard Transforms (RHTs) have emerged as a computationally ...
research
∙
03/01/2022
Private Frequency Estimation via Projective Geometry
In this work, we propose a new algorithm ProjectiveGeometryResponse (PGR...
research
∙
02/28/2022
On the Robustness of CountSketch to Adaptive Inputs
CountSketch is a popular dimensionality reduction technique that maps ve...
research
∙
10/17/2021
Terminal Embeddings in Sublinear Time
Recently (Elkin, Filtser, Neiman 2017) introduced the concept of a termi...
research
∙
07/06/2021
Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020
Theoretical computer science (TCS) is a subdiscipline of computer scienc...
research
∙
04/19/2021
Randomized Algorithms for Scientific Computing (RASC)
Randomized algorithms have propelled advances in artificial intelligence...
research
∙
10/25/2020
An Improved Sketching Bound for Edit Distance
We provide improved upper bounds for the simultaneous sketching complexi...
research
∙
10/21/2020
On Adaptive Distance Estimation
We provide a static data structure for distance estimation which support...
research
∙
10/05/2020
Optimal bounds for approximate counting
Storing a counter incremented N times would naively consume O(log N) bit...
research
∙
09/27/2019
Margin-Based Generalization Lower Bounds for Boosted Classifiers
Boosting is one of the most successful ideas in machine learning. The mo...
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
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
We show optimal lower bounds for spanning forest computation in two diff...
research
∙
11/13/2017
Heavy Hitters and the Structure of Local Privacy
We present a new locally differentially private algorithm for the heavy ...
research
∙
07/08/2015
Optimal approximate matrix product in terms of stable rank
We prove, using the subspace embedding guarantee in a black box way, tha...
research
∙
11/11/2013