b'Rasmus Pagh'

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...

0 Kasper Green Larsen, et al. ∙

research

∙ 06/16/2023

A Smooth Binary Mechanism for Efficient Private Continual Observation

In privacy under continual observation we study how to release different...

0 Joel Daniel Andersson, et al. ∙

research

∙ 06/14/2023

PLAN: Variance-Aware Private Mean Estimation

Differentially private mean estimation is an important building block in...

0 Martin Aumüller, et al. ∙

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...

0 Ivan Damgård, et al. ∙

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...

0 David Rasmussen Lolck, et al. ∙

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...

0 Praneeth Kacham, et al. ∙

research

∙ 11/07/2022

Simple Set Sketching

Imagine handling collisions in a hash table by storing, in each cell, th...

0 Jakob Bæk Tejs Houen, et al. ∙

research

∙ 05/30/2022

Daisy Bloom Filters

Weighted Bloom filters (Bruck, Gao and Jiang, ISIT 2006) are Bloom filte...

0 Ioana O. Bercea, et al. ∙

research

∙ 05/23/2022

HyperLogLogLog: Cardinality Estimation With One Log More

We present HyperLogLogLog, a practical compression of the HyperLogLog sk...

0 Matti Karppa, et al. ∙

research

∙ 05/17/2022

Improved Utility Analysis of Private CountSketch

Sketching is an important tool for dealing with high-dimensional vectors...

0 Rasmus Pagh, et al. ∙

research

∙ 10/13/2021

Infinitely Divisible Noise in the Low Privacy Regime

Federated learning, in which training data is distributed among users an...

0 Rasmus Pagh, et al. ∙

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...

0 Badih Ghazi, et al. ∙

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...

0 Matti Karppa, et al. ∙

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...

0 Martin Aumüller, et al. ∙

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...

0 Badih Ghazi, et al. ∙

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...

0 Kasper Green Larsen, et al. ∙

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...

0 Martin Aumüller, et al. ∙

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...

2 Edith Cohen, et al. ∙

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...

0 Edith Cohen, et al. ∙

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...

0 Mayank Goswami, et al. ∙

research

∙ 02/05/2020

Pure Differentially Private Summation from Anonymous Messages

The shuffled (aka anonymous) model has recently generated significant in...

0 Badih Ghazi, et al. ∙

research

∙ 01/31/2020

Efficient Differentially Private F_0 Linear Sketching

A powerful feature of linear sketches is that from sketches of two data ...

0 Rasmus Pagh, et al. ∙

research

∙ 12/10/2019

Advances and Open Problems in Federated Learning

Federated learning (FL) is a machine learning setting where many clients...

33 Peter Kairouz, et al. ∙

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 ...

0 Badih Ghazi, et al. ∙

research

∙ 09/24/2019

The space complexity of inner product filters

Motivated by the problem of filtering candidate pairs in inner product s...

0 Rasmus Pagh, et al. ∙

research

∙ 09/03/2019

Oblivious Sketching of High-Degree Polynomial Kernels

Kernel methods are fundamental tools in machine learning that allow dete...

0 Michael Kapralov, et al. ∙

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...

0 Badih Ghazi, et al. ∙

research

∙ 07/04/2019

Hardness of Bichromatic Closest Pair with Jaccard Similarity

Consider collections A and B of red and blue sets, respectively. Bichrom...

0 Rasmus Pagh, et al. ∙

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...

0 Martin Aumüller, et al. ∙

research

∙ 06/19/2019

Scalable and Differentially Private Distributed Aggregation in the Shuffled Model

Federated learning promises to make machine learning feasible on distrib...

0 Badih Ghazi, et al. ∙

research

∙ 06/05/2019

Fair Near Neighbor Search: Independent Range Sampling in High Dimensions

Similarity search is a fundamental algorithmic primitive, widely used in...

0 Martin Aumüller, et al. ∙

research

∙ 12/06/2018

Confirmation Sampling for Exact Nearest Neighbor Search

Locality-sensitive hashing (LSH), introduced by Indyk and Motwani in STO...

0 Tobias Christiani, et al. ∙

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 ...

0 Djamal Belazzougui, et al. ∙

research

∙ 04/09/2018

Set Similarity Search for Skewed Data

Set similarity join, as well as the corresponding indexing problem set s...

0 Samuel McCauley, et al. ∙

research

∙ 02/18/2018

Scalable Alignment Kernels via Space-Efficient Feature Maps

String kernels are attractive data analysis tools for analyzing string d...

0 Yasuo Tabei, et al. ∙

research

∙ 07/21/2017

Scalable and robust set similarity join

Set similarity join is a fundamental and well-studied database operator....

0 Tobias Christiani, et al. ∙

Rasmus Pagh

Featured Co-authors