Kasper Green Larsen | |
Assistant Professor, Ph.D. | |
MADALGO (Center for Massive Data Algorithmics) | |
Department of Computer Science | |
Aarhus University | |
Contact Information | |
Mail: larsen@cs.au.dk |
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Kasper Green Larsen, Omri Weinstein, Huacheng Yu Manuscript. |
Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D
Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen, Stefan Schneider, Mingzhou Song Manuscript. |
A Dichotomy for Regular Expression Membership Testing
Karl Bringmann, Allan Grønlund, Kasper Green Larsen Manuscript. |
Optimality of the Johnson-Lindenstrauss Lemma
Kasper Green Larsen, Jelani Nelson Manuscript. |
DecreaseKeys are Expensive for External Memory Priority Queues
Kasper Eenberg, Kasper Green Larsen, Huacheng Yu STOC'17: 49th ACM Symposium on Theory of Computing. |
Faster Online Matrix-Vector Multiplication
Kasper Green Larsen, Ryan Williams SODA'17: 28th ACM-SIAM Symposium on Discrete Algorithms. |
Heavy Hitters via Cluster-Preserving Clustering
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyễn, Mikkel Thorup FOCS'16: 57th IEEE Symposium on Foundations of Computer Science. |
How to Prove Knowledge of Small Secrets
Carsten Baum, Ivan Damgård, Kasper Green Larsen, Michael Nielsen CRYPTO'16: 36th International Cryptology Conference. |
Towards Tight Lower Bounds for Range Reporting on the RAM
Allan Grønlund, Kasper Green Larsen ICALP'16: 43rd International Colloquium on Automata, Languages and Programming. |
The Johnson-Lindenstrauss Lemma is Optimal for Linear Dimensionality Reduction
Kasper Green Larsen, Jelani Nelson ICALP'16: 43rd International Colloquium on Automata, Languages and Programming. |
New Unconditional Hardness Results for Dynamic and Online Problems
Raphael Clifford, Allan Grønlund, Kasper Green Larsen FOCS'15: 56th IEEE Symposium on Foundations of Computer Science. |
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
Joshua Brody, Kasper Green Larsen ToC: Theory of Computing. Vol 11, 2015. To appear. |
Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyễn STOC'15: 47th ACM Symposium on Theory of Computing. |
Approximate Range Emptiness in Constant Time and Optimal Space
Mayank Goswami, Allan Grønlund, Kasper Green Larsen, Rasmus Pagh SODA'15: 26th ACM-SIAM Symposium on Discrete Algorithms. |
Optimal Planar Orthogonal Skyline Counting Queries
Gerth Stølting Brodal, Kasper Green Larsen SWAT'14: 14th Scandinavian Symposium and Workshops on Algorithm Theory. |
On Hardness of Several String Problems
Kasper Green Larsen, J. Ian Munro, Jesper Sindahl Nielsen, Sharma V. Thankachan CPM'14: 25th Symposium on Combinatorial Pattern Matching. |
Near-Optimal Labeling Schemes for Nearest Common Ancestors
Stephen Alstrup, Esben Bistrup Halvorsen, Kasper Green Larsen SODA'14: 25th ACM-SIAM Symposium on Discrete Algorithms. |
Models and Techniques for Proving Data Structure Lower Bounds
Kasper Green Larsen PhD Dissertation. Handed in February 28th, 2013. Successfully defended May 17th, 2013. Co-winner of the Aarhus University Ph.D. Prize. |
Succinct Sampling from Discrete Distributions
Karl Bringmann, Kasper Green Larsen STOC'13: 45th ACM Symposium on Theory of Computing. |
The Query Complexity of Finding a Hidden Permutation
Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, Kurt Mehlhorn LNCS: Space-Efficient Data Structures, Streams and Algorithms. Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. LNCS Vol. 8066, 2013. |
Near-Optimal Range Reporting Structures for Categorical Data
Kasper Green Larsen, Freek van Walderveen SODA'13: 24th ACM-SIAM Symposium on Discrete Algorithms. |
I/O-Efficient Spatial Data Structures for Range Queries
Lars Arge, Kasper Green Larsen Invited abstract in SIGSPATIAL Special, July, 2012. |
Higher Cell Probe Lower Bounds for Evaluating Polynomials
Kasper Green Larsen FOCS'12: 53rd IEEE Symposium on Foundations of Computer Science. |
Improved Range Searching Lower Bounds
Kasper Green Larsen, Huy L. Nguyễn SoCG'12: 28th ACM Symposium on Computational Geometry. Some of the bounds obtained in this paper are superseded in the newest (journal) version of 9. |
Higher-dimensional Orthogonal Range Reporting and Rectangle Stabbing in the Pointer Machine Model
Peyman Afshani, Lars Arge, Kasper Green Larsen SoCG'12: 28th ACM Symposium on Computational Geometry. |
The Cell Probe Complexity of Dynamic Range Counting
Kasper Green Larsen STOC'12: 44th ACM Symposium on Theory of Computing. Co-winner of the Best Paper Award and winner of the Best Student Paper Award (the Danny Lewin Award). Invited to Journal of the ACM (JACM). |
Linear-Space Data Structures for Range Mode Query in Arrays
Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, Bryan T. Wilkinson STACS'12: 29th Symposium on Theoretical Aspects of Computer Science. Invited to special issue of Theory of Computing Systems (TOCS). |
I/O-Efficient Data Structures for Colored Range and Prefix Reporting
Kasper Green Larsen, Rasmus Pagh SODA'12: 23rd ACM-SIAM Symposium on Discrete Algorithms. |
On Range Searching in the Group Model and Combinatorial Discrepancy
Kasper Green Larsen FOCS'11: 52nd IEEE Symposium on Foundations of Computer Science. Co-winner of the Best Student Paper Award (the Machtey Award). Invited to special issue of SIAM Journal on Computing (SICOMP). |
Orthogonal Range Searching on the RAM, Revisited
Timothy M. Chan, Kasper Green Larsen, Mihai Pătraşcu SoCG'11: 27th ACM Symposium on Computational Geometry. Invited to special issue of Computational Geometry: Theory and Applications (CGTA); declined. |
(Approximate) Uncertain Skylines
Peyman Afshani, Pankaj K. Agarwal, Lars Arge, Kasper Green Larsen, Jeff M. Phillips ICDT'11: 14th International Conference on Database Theory. Invited to special issue of Theory of Computing Systems (TOCS). |
Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures
Allan Grønlund Jørgensen, Kasper Green Larsen SODA'11: 22nd ACM-SIAM Symposium on Discrete Algorithms. |
Cleaning Massive Sonar Point Clouds
Lars Arge, Kasper Green Larsen, Thomas Mølhave, Freek van Walderveen GIS'10: 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. |
Cell Probe Lower Bounds and Approximations for Range Mode
Mark Greve, Allan Grønlund Jørgensen, Kasper Dalgaard Larsen, Jakob Truelsen ICALP'10: 37th International Colloquium on Automata, Languages and Programming. |
Orthogonal Range Reporting: Query Lower Bounds, Optimal Structures in 3-d, and Higher-dimensional Improvements
Peyman Afshani, Lars Arge, Kasper Dalgaard Larsen SoCG'10: 26th ACM Symposium on Computational Geometry. Invited to special issue of Computational Geometry: Theory and Applications (CGTA); declined. |
Orthogonal Range Reporting in Three and Higher Dimensions
Peyman Afshani, Lars Arge, Kasper Dalgaard Larsen FOCS'09: 50th IEEE Symposium on Foundations of Computer Science. |
Mental Models and Programming Aptitude
Michael E. Caspersen, Jens Bennedsen, Kasper Dalgaard Larsen ITiCSE'07: 12th Conference on Innovation and Technology in Computer Science Education. |