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


I'm an Assistant Professor at the Department of Computer Science at Aarhus University. My main research area is data structures, with an emphasis on range searching and lower bounds.

Teaching:


Grants:


Awards:

  1. Aarhus University Ph.D. Prize 2014
  2. STOC Best Paper Award 2012
  3. STOC Best Student Paper Award 2012 (The Danny Lewin Award)
  4. FOCS Best Student Paper Award 2011 (The Machtey Award)
  5. Danish Minister of Science's Elite Research (EliteForsk) Travel Scholarship 2011
  6. Google European Doctoral Fellowship 2010

Committees:


Ph.D. Students:


Links:

  1. My Google Scholar Profile

Publications:

Click on the titles to display abstracts
  1. Faster Online Matrix-Vector Multiplication
    Kasper Green Larsen, Ryan Williams
    Manuscript.
  2. DecreaseKeys are Expensive for External Memory Priority Queues
    Kasper Eenberg, Kasper Green Larsen, Huacheng Yu
    Manuscript.
  3. 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.
  4. How to Prove Knowledge of Small Secrets
    Carsten Baum, Ivan Damgård, Kasper Green Larsen, Michael Nielsen
    CRYPTO'16: 36th International Cryptology Conference.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. Optimal Planar Orthogonal Skyline Counting Queries
    Gerth Stølting Brodal, Kasper Green Larsen
    SWAT'14: 14th Scandinavian Symposium and Workshops on Algorithm Theory.
  12. 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.
  13. 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.
  14. 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.
  15. Succinct Sampling from Discrete Distributions
    Karl Bringmann, Kasper Green Larsen
    STOC'13: 45th ACM Symposium on Theory of Computing.
  16. 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.
  17. Near-Optimal Range Reporting Structures for Categorical Data
    Kasper Green Larsen, Freek van Walderveen
    SODA'13: 24th ACM-SIAM Symposium on Discrete Algorithms.
  18. I/O-Efficient Spatial Data Structures for Range Queries
    Lars Arge, Kasper Green Larsen
    Invited abstract in SIGSPATIAL Special, July, 2012.
  19. Higher Cell Probe Lower Bounds for Evaluating Polynomials
    Kasper Green Larsen
    FOCS'12: 53rd IEEE Symposium on Foundations of Computer Science.
  20. 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.
  21. 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.
  22. 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).
  23. 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).
  24. 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.
  25. 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).
  26. 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.
  27. (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).
  28. 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.
  29. 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.
  30. 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.
  31. 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.
  32. 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.
  33. 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.