48 citations · 181 across the 49 of their papers we have counts for
5 papers · 1 filter
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,…
Constructive Discrepancy Minimization with Hereditary L2 Guarantees
Kasper Green Larsen
In discrepancy minimization problems, we are given a family of sets , with each a subset of some universe $U = \{u_1,\dots,u_…
On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms
Casper Benjamin Freksen, Kasper Green Larsen
The Johnson-Lindenstrauss lemma is one of the corner stone results in dimensionality reduction. It says that given , for any set of vectors , there e…
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in d…
Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D
Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen +3
The -Means clustering problem on points is NP-Hard for any dimension , however, for the 1D case there exists exact polynomial time algorithms. Previous literature re…