48 citations · 181 across the 49 of their papers we have counts for
56 papers
The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting
Konstantina Bairaktari, Kasper Green Larsen, Markus Engelund Dahl
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,…
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…
Sublinear Time Shortest Path in Expander Graphs
Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen +1
Computing a shortest path between two nodes in an undirected unweighted graph is among the most basic algorithmic tasks. Breadth first search solves this problem in linear time, wh…
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…
Super-Logarithmic Lower Bounds for Dynamic Graph Problems
Kasper Green Larsen, Huacheng Yu
In this work, we prove a unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability quer…
Sparse Dimensionality Reduction Revisited
Mikael Møller Høgsgaard, Lion Kamma, Kasper Green Larsen +2
The sparse Johnson-Lindenstrauss transform is one of the central techniques in dimensionality reduction. It supports embedding a set of points in into $m=O(\vare…
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…
The Impossibility of Parallelizing Boosting
Amin Karbasi, Kasper Green Larsen
The aim of boosting is to convert a sequence of weak learners into a strong learner. At their heart, these methods are fully sequential. In this paper, we investigate the possibili…
Bagging is an Optimal PAC Learner
Kasper Green Larsen
Determining the optimal sample complexity of PAC learning in the realizable setting was a central open problem in learning theory for decades. Finally, the seminal work by Hanneke…
Hierarchical Categories in Colored Searching
Peyman Afshani, Rasmus Killman, Kasper Green Larsen
In colored range counting (CRC), the input is a set of points where each point is assigned a ``color'' (or a ``category'') and the goal is to store them in a data structure such th…
Barriers for Faster Dimensionality Reduction
Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
The Johnson-Lindenstrauss transform allows one to embed a dataset of points in into while preserving the pairwise distance between any pair of po…
Fast Discrepancy Minimization with Hereditary Guarantees
Kasper Green Larsen
Efficiently computing low discrepancy colorings of various set systems, has been studied extensively since the breakthrough work by Bansal (FOCS 2010), who gave the first polynomia…
Optimal Weak to Strong Learning
Kasper Green Larsen, Martin Ritzert
The classic algorithm AdaBoost allows to convert a weak learner, that is an algorithm that produces a hypothesis which is slightly better than chance, into a strong learner, achiev…
The Fast Johnson-Lindenstrauss Transform is Even Faster
Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
The seminal Fast Johnson-Lindenstrauss (Fast JL) transform by Ailon and Chazelle (SICOMP'09) embeds a set of points in -dimensional Euclidean space into optimal $k=O(\vareps…
Stronger 3SUM-Indexing Lower Bounds
Eldon Chung, Kasper Green Larsen
The SUM-Indexing problem was introduced as a data structure version of the SUM problem, with the goal of proving strong conditional lower bounds for static data structures vi…
Towards Optimal Lower Bounds for k-median and k-means Coresets
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic +1
Given a set of points in a metric space, the -clustering problem consists of finding a set of points called centers, such that the sum of distances raised to the power o…
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures
Yair Bartal, Ora Nova Fandina, Kasper Green Larsen
It is well known that the Johnson-Lindenstrauss dimensionality reduction method is optimal for worst case distortion. While in practice many other methods and heuristics are used,…
Compression Implies Generalization
Allan Grønlund, Mikael Høgsgaard, Lior Kamma +1
Explaining the surprising generalization performance of deep neural networks is an active and important line of research in theoretical machine learning. Influential work by Arora…
Property-Preserving Hash Functions from Standard Assumptions
Nils Fleischhacker, Kasper Green Larsen, and Mark Simkin
Property-preserving hash functions allow for compressing long inputs and into short hashes and in a manner that allows for computing a predicate $P(x_…
CountSketches, Feature Hashing and the Median of Three
Kasper Green Larsen, Rasmus Pagh, Jakub Tětek
In this paper, we revisit the classic CountSketch method, which is a sparse, random projection that transforms a (high-dimensional) Euclidean vector to a vector of dimension $(…
Margins are Insufficient for Explaining Gradient Boosting
Allan Grønlund, Lior Kamma, Kasper Green Larsen
Boosting is one of the most successful ideas in machine learning, achieving great practical performance with little fine-tuning. The success of boosted classifiers is most often at…
Further Unifying the Landscape of Cell Probe Lower Bounds
Kasper Green Larsen, Jonathan Lindegaard Starup, Jesper Steensgaard
In a landmark paper, Pǎtraşcu demonstrated how a single lower bound for the static data structure problem of reachability in the butterfly graph, could be used to derive a wealth o…
Near-Tight Margin-Based Generalization Bounds for Support Vector Machines
Allan Grønlund, Lior Kamma, Kasper Green Larsen
Support Vector Machines (SVMs) are among the most fundamental tools for binary classification. In its simplest formulation, an SVM produces a hyperplane separating two classes of d…
Optimal Learning of Joint Alignments with a Faulty Oracle
Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis
We consider the following problem, which is useful in applications such as joint image and shape alignment. The goal is to recover discrete variables $g_i \in \{0, \ldots, k-1\…