33 citations · 47 across the 16 of their papers we have counts for
15 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…
Revisiting Agnostic PAC Learning
Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy
PAC learning, dating back to Valiant'84 and Vapnik and Chervonenkis'64,'74, is a classic model for studying supervised learning. In the agnostic setting, we have access to a hypoth…
Majority-of-Three: The Simplest Optimal Learner?
Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen +1
Developing an optimal PAC learning algorithm in the realizable setting, where empirical risk minimization (ERM) is suboptimal, was a major open problem in learning theory for decad…
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…
Super-Logarithmic Lower Bounds for Dynamic Graph Problems
Kasper Green Larsen, Huacheng Yu
In this work, we prove a unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability quer…
Sparse Dimensionality Reduction Revisited
Mikael Møller Høgsgaard, Lion Kamma, Kasper Green Larsen +2
The sparse Johnson-Lindenstrauss transform is one of the central techniques in dimensionality reduction. It supports embedding a set of points in into $m=O(\vare…