11 citations · 41 across the 17 of their papers we have counts for
29 papers
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…
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…
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…
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 $(…