3 citations · 4 across the 3 of their papers we have counts for
4 papers
A new lower bound for multi-color discrepancy with applications to fair division
Ioannis Caragiannis, Kasper Green Larsen, Sudarshan Shyam
A classical problem in combinatorics seeks colorings of low discrepancy. More concretely, the goal is to color the elements of a set system so that the number of appearances of any…
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…
Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
Karl Bringmann, Kasper Green Larsen, André Nusser +2
Union volume estimation is a classical algorithmic problem. Given a family of objects , we want to approximate the volume of their union. In…
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
Karl Bringmann, Allan Grønlund, Marvin Künnemann +1
We pose the fine-grained hardness hypothesis that the textbook algorithm for the NFA Acceptance problem is optimal up to subpolynomial factors, even for dense NFAs and fixed alphab…