48 citations · 53 across the 6 of their papers we have counts for
7 papers
An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
Allan Grønlund, Kasper Green Larsen
Achieving a provable exponential quantum speedup for an important machine learning task has been a central research goal since the seminal HHL quantum algorithm for solving linear…
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…
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…
Explaining the poor performance of the KASS algorithm implementation
Allan Grønlund
By investigating the code for the KASS algorithm implementation used in the paper "Exploring the quantum speed limit with computer games" [1, arXiv:1506.09091] by Sørensen et al. (…
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…
A Dichotomy for Regular Expression Membership Testing
Karl Bringmann, Allan Grønlund, Kasper Green Larsen
We study regular expression membership testing: Given a regular expression of size and a string of size , decide whether the string is in the language described by the regul…
Threesomes, Degenerates, and Love Triangles
Allan Grønlund, Seth Pettie
The 3SUM problem is to decide, given a set of real numbers, whether any three sum to zero. It is widely conjectured that a trivial -time algorithm is optimal and over t…