48 citations · 181 across the 49 of their papers we have counts for
41 papers · 1 filter
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…
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…
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,…
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 $(…
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…
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\…
Lower Bounds for Oblivious Near-Neighbor Search
Kasper Green Larsen, Tal Malkin, Omri Weinstein +1
We prove an lower bound on the dynamic cell-probe complexity of statistically approximate-near-neighbor search () over…
Lower Bounds for Multiplication via Network Coding
Peyman Afshani, Casper Benjamin Freksen, Lior Kamma +1
Multiplication is one of the most fundamental computational problems, yet its true complexity remains elusive. The best known upper bound, by Fürer, shows that two -bit numbers…
The Query Complexity of a Permutation-Based Variant of Mastermind
Peyman Afshani, Manindra Agrawal, Benjamin Doerr +3
We study the query complexity of a permutation-based variant of the guessing game Mastermind. In this variant, the secret is a pair which consists of a binary string $z \in…
Lower Bounds for External Memory Integer Sorting via Network Coding
Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen +1
Sorting extremely large datasets is a frequently occuring task in practice. These datasets are usually much larger than the computer's main memory; thus external memory sorting alg…
Lower Bounds for Oblivious Data Structures
Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen
An oblivious data structure is a data structure where the memory access patterns reveals no information about the operations performed on it. Such data structures were introduced b…
A Faster External Memory Priority Queue with DecreaseKeys
Shunhua Jiang, Kasper Green Larsen
A priority queue is a fundamental data structure that maintains a dynamic set of (key, priority)-pairs and supports Insert, Delete, ExtractMin and DecreaseKey operations. In the ex…
Upper and lower bounds for dynamic data structures on strings
Raphael Clifford, Allan Grønlund, Kasper Green Larsen +1
We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the patte…
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen
The conjectured hardness of Boolean matrix-vector multiplication has been used with great success to prove conditional lower bounds for numerous important data structure problems,…