research
∙
08/30/2023
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
We present a simple and provably optimal non-adaptive cell probe data st...
share
research
∙
06/16/2023
A Smooth Binary Mechanism for Efficient Private Continual Observation
In privacy under continual observation we study how to release different...
research
∙
06/14/2023
PLAN: Variance-Aware Private Mean Estimation
Differentially private mean estimation is an important building block in...
research
∙
06/07/2023
Differentially Private Selection from Secure Distributed Computing
Given a collection of vectors x^(1),…,x^(n)∈{0,1}^d, the selection probl...
research
∙
05/04/2023
Shannon meets Gray: Noise-robust, Low-sensitivity Codes with Applications in Differential Privacy
Integer data is typically made differentially private by adding noise fr...
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
∙
11/07/2022
Simple Set Sketching
Imagine handling collisions in a hash table by storing, in each cell, th...
research
∙
05/30/2022
Daisy Bloom Filters
Weighted Bloom filters (Bruck, Gao and Jiang, ISIT 2006) are Bloom filte...
research
∙
05/23/2022
HyperLogLogLog: Cardinality Estimation With One Log More
We present HyperLogLogLog, a practical compression of the HyperLogLog sk...
research
∙
05/17/2022
Improved Utility Analysis of Private CountSketch
Sketching is an important tool for dealing with high-dimensional vectors...
research
∙
10/13/2021
Infinitely Divisible Noise in the Low Privacy Regime
Federated learning, in which training data is distributed among users an...
research
∙
09/27/2021
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message
The shuffle model of differential privacy has attracted attention in the...
research
∙
07/06/2021
DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search
Kernel Density Estimation (KDE) is a nonparametric method for estimating...
research
∙
06/18/2021
Differentially private sparse vectors with low error, optimal space, and fast access
Representing a sparse histogram, or more generally a sparse vector, is a...
research
∙
06/08/2021
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead
Differential privacy (DP) is a formal notion for quantifying the privacy...
research
∙
02/03/2021
CountSketches, Feature Hashing and the Median of Three
In this paper, we revisit the classic CountSketch method, which is a spa...
research
∙
01/26/2021
Sampling a Near Neighbor in High Dimensions – Who is the Fairest of Them All?
Similarity search is a fundamental algorithmic primitive, widely used in...
research
∙
07/14/2020
WOR and p's: Sketches for ℓ_p-Sampling Without Replacement
Weighted sampling is a fundamental tool in data analysis and machine lea...
research
∙
04/09/2020
Composable Sketches for Functions of Frequencies: Beyond the Worst Case
Recently there has been increased interest in using machine learning tec...
research
∙
02/12/2020
On the I/O complexity of the k-nearest neighbor problem
We consider static, external memory indexes for exact and approximate ve...
research
∙
02/05/2020
Pure Differentially Private Summation from Anonymous Messages
The shuffled (aka anonymous) model has recently generated significant in...
research
∙
01/31/2020
Efficient Differentially Private F_0 Linear Sketching
A powerful feature of linear sketches is that from sketches of two data ...
research
∙
12/10/2019
Advances and Open Problems in Federated Learning
Federated learning (FL) is a machine learning setting where many clients...
research
∙
09/24/2019
Private Aggregation from Fewer Anonymous Messages
Consider the setup where n parties are each given a number x_i ∈F_q and ...
research
∙
09/24/2019
The space complexity of inner product filters
Motivated by the problem of filtering candidate pairs in inner product s...
research
∙
09/03/2019
Oblivious Sketching of High-Degree Polynomial Kernels
Kernel methods are fundamental tools in machine learning that allow dete...
research
∙
08/29/2019
Private Heavy Hitters and Range Queries in the Shuffled Model
An exciting new development in differential privacy is the shuffled mode...
research
∙
07/04/2019
Hardness of Bichromatic Closest Pair with Jaccard Similarity
Consider collections A and B of red and blue sets, respectively. Bichrom...
research
∙
06/28/2019
PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors
We present PUFFINN, a parameterless LSH-based index for solving the k-ne...
research
∙
06/19/2019
Scalable and Differentially Private Distributed Aggregation in the Shuffled Model
Federated learning promises to make machine learning feasible on distrib...
research
∙
06/05/2019
Fair Near Neighbor Search: Independent Range Sampling in High Dimensions
Similarity search is a fundamental algorithmic primitive, widely used in...
research
∙
12/06/2018
Confirmation Sampling for Exact Nearest Neighbor Search
Locality-sensitive hashing (LSH), introduced by Indyk and Motwani in STO...
research
∙
04/12/2018
Fast Prefix Search in Little Space, with Applications
It has been shown in the indexing literature that there is an essential ...
research
∙
04/09/2018
Set Similarity Search for Skewed Data
Set similarity join, as well as the corresponding indexing problem set s...
research
∙
02/18/2018
Scalable Alignment Kernels via Space-Efficient Feature Maps
String kernels are attractive data analysis tools for analyzing string d...
research
∙
07/21/2017