Kasper Green Larsen

activity

20112026

most citedFast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D

48 citations · 181 across the 49 of their papers we have counts for

collaborators

Showing 2019 · cs.DSShow all

3 papers · 2 filters

cs.DS2019

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 $n$ discrete variables $g_i \in \{0, \ldots, k-1\…

cs.DS2019

Lower Bounds for Oblivious Near-Neighbor Search

Kasper Green Larsen, Tal Malkin, Omri Weinstein +1

We prove an $Ω (d l g n / (l g l g n)^{2})$ lower bound on the dynamic cell-probe complexity of statistically $oblivious$ approximate-near-neighbor search ( $ANN$ ) over…

cs.DS2019★ 4 cited

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 $n$ -bit numbers…