4 papers
The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting
Konstantina Bairaktari, Kasper Green Larsen
Private continual counting is a fundamental problem in differential privacy: given a binary stream of length , where each corresponds to the contribution of one individual,…
AdaBoost is not an Optimal Weak to Strong Learner
Mikael Møller Høgsgaard, Kasper Green Larsen, Martin Ritzert
AdaBoost is a classic boosting algorithm for combining multiple inaccurate classifiers produced by a weak learner, to produce a strong learner with arbitrarily high accuracy when g…
Invertible Bloom Lookup Tables with Less Memory and Randomness
Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski +1
In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities. IBLTs are highly versatile data structures that have found applications in set reconc…
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano +3
We present a simple and provably optimal non-adaptive cell probe data structure for the static dictionary problem. Our data structure supports storing a set of n key-value pairs fr…