Photo: Tariq Mikkel Khan
Kasper Green Larsen
Professor, Ph.D.
Department of Computer Science
Aarhus University

Contact Information
Mail: larsen@cs.au.dk


I'm a Full Professor at the Department of Computer Science at Aarhus University where I head the Algorithms, Data Structures and Foundations of Machine Learning research group. My research interests span many areas of theoretical computer science, including theory of machine learning, data structures, algorithms, lower bounds and cryptography. I also serve as a Senior Scientific Expert at the Quantum and HPC startup Kvantify.

I received my Ph.D. from Aarhus University in 2013, under the supervision of Professor Lars Arge. I had the pleasure of being a member of the Young Academy under the Royal Danish Academy of Sciences and Letters from 2017-2022.

My CV is here. You can find more information about my publications, awards, etc. further down this page.

Awards:

  1. COLT Best Paper Award 2023
  2. Presburger Award 2019
  3. CRYPTO Best Paper Award 2018
  4. Teacher of the Year Award 2018
  5. Hartmann Diploma Prize 2017
  6. Aarhus University Ph.D. Prize 2014
  7. STOC Best Paper Award 2012
  8. STOC Best Student Paper Award 2012 (The Danny Lewin Award)
  9. FOCS Best Student Paper Award 2011 (The Machtey Award)
  10. Danish Minister of Science's Elite Research (EliteForsk) Travel Scholarship 2011
  11. Google European Doctoral Fellowship 2010

Post Docs:


Ph.D. Students:


Links:

  1. Google Scholar Profile
  2. Twitter
  3. YouTube Channel
  4. CV

Publications:

Click on the titles to display abstracts.
Note: In theoretical computer science, we always list authors alphabetically by last name. Publications not following this rule are marked with * at the end of their title.
  1. Majority-of-Three: The Simplest Optimal Learner?
    Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy
    Manuscript.
  2. Replicable Learning of Large-Margin Halfspaces
    Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, Felix Zhou
    Manuscript.
  3. Boosting, Voting Classifiers and Randomized Sample Compression Schemes
    Arthur da Cunha, Kasper Green Larsen, Martin Ritzert
    Manuscript.
  4. Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
    Kasper Green Larsen, Rasmus Pagh, Toniann Pitassi, Or Zamir
    Manuscript.
  5. Sublinear Time Shortest Path in Expander Graphs
    Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen
    Manuscript.
  6. Invertible Bloom Lookup Tables with Less Memory and Randomness
    Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin
    Manuscript.
  7. Sparse Dimensionality Reduction Revisited
    Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, Chris Schwiegelshohn
    Manuscript.
  8. The Impossibility of Parallelizing Boosting
    Amin Karbasi, Kasper Green Larsen
    ALT'24: 35th Conference on Algorithmic Learning Theory.
  9. Diagonalization Games
    Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran
    AMM'24: American Mathematical Monthly. Expected to appear in 2024.
  10. The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
    Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
    ITCS'24: 15th Innovations in Theoretical Computer Science.
  11. Super-Logarithmic Lower Bounds for Dynamic Graph Problems
    Kasper Green Larsen, Huacheng Yu
    FOCS'23: 64th IEEE Symposium on Foundations of Computer Science.
    Invited to special issue of SIAM Journal on Computing (SICOMP).
  12. Bagging is an Optimal PAC Learner
    Kasper Green Larsen
    COLT'23: 36th Conference on Learning Theory.
    Winner of the Best Paper Award.
  13. AdaBoost is not an Optimal Weak to Strong Learner
    Mikael Møller Høgsgaard, Kasper Green Larsen, Martin Ritzert
    ICML'23: 40th International Conference on Machine Learning.
    Accepted for Short Live presentation.
  14. The Fast Johnson-Lindenstrauss Transform is Even Faster
    Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
    ICML'23: 40th International Conference on Machine Learning.
  15. Distributed Shuffling in Adversarial Environments
    Kasper Green Larsen, Maciej Obremski, Mark Simkin
    ITC'23: 4th Information-Theoretic Cryptography Conference.
  16. How to Compress Encrypted Data
    Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
    EUROCRYPT'23: 42nd Conference on the Theory and Applications of Cryptology and Information Security.
  17. Barriers for Faster Dimensionality Reduction
    Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
    STACS'23: 40th Symposium on Theoretical Aspects of Computer Science.
  18. Fast Discrepancy Minimization with Hereditary Guarantees
    Kasper Green Larsen
    SODA'23: 34th ACM-SIAM Symposium on Discrete Algorithms.
  19. Stronger 3SUM-Indexing Lower Bounds
    Eldon Chung, Kasper Green Larsen
    SODA'23: 34th ACM-SIAM Symposium on Discrete Algorithms.
  20. Optimal Weak to Strong Learning
    Kasper Green Larsen, Martin Ritzert
    NeurIPS'22: 36th Conference on Neural Information Processing Systems.
  21. Improved Coresets for Euclidean k-Means
    Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar
    NeurIPS'22: 36th Conference on Neural Information Processing Systems.
  22. Hierarchical Categories in Colored Searching
    Peyman Afshani, Rasmus Killmann, Kasper Green Larsen
    ISAAC'22: 33rd International Symposium on Algorithms and Computation.
    Invited to special issue of Computational Geometry: Theory and Applications (CGTA).
  23. Towards Optimal Lower Bounds for k-median and k-means Coresets
    Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn
    STOC'22: 54th ACM Symposium on Theory of Computing.
  24. Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures
    Yair Bartal, Ora Nova Fandina, Kasper Green Larsen
    SoCG'22: 38th ACM Symposium on Computational Geometry.
    Invited to special issue of Journal of Computational Geometry (JoCG). Declined
  25. Property-Preserving Hash Functions for Hamming Distance from Standard Assumptions
    Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
    EUROCRYPT'22: 41st Conference on the Theory and Applications of Cryptology and Information Security.
  26. CountSketches, Feature Hashing and the Median of Three
    Kasper Green Larsen, Rasmus Pagh, Jakub Tětek
    ICML'21: 38th International Conference on Machine Learning.
  27. Broadcast Secret-Sharing, Bounds and Applications
    Ivan Damgård, Kasper Green Larsen, Sophia Yakoubov
    ITC'21: 2nd Information-Theoretic Cryptography Conference.
  28. Further Unifying the Landscape of Cell Probe Lower Bounds
    Kasper Green Larsen, Jonathan Lindegaard Starup, Jesper Steensgaard
    SOSA'21: 3rd Symposium on Simplicity in Algorithms.
  29. Optimal Oblivious Priority Queues
    Zahra Jafargholi, Kasper Green Larsen, Mark Simkin
    SODA'21: 32nd ACM-SIAM Symposium on Discrete Algorithms.
  30. Predicting Positive and Negative Links with Noisy Queries: Theory and Practice*
    Charalampos E. Tsourakakis, Michael Mitzenmacher, Kasper Green Larsen, Jaroslaw Blasiok, Ben Lawson, Preetum Nakkiran, Vasileios Nakos
    Internet Mathematics 2020.
  31. Margins are Insufficient for Explaining Gradient Boosting
    Allan Grønlund, Lior Kamma, Kasper Green Larsen
    NeurIPS'20: 34th Conference on Neural Information Processing Systems.
  32. Lower Bounds for Multi-Server Oblivious RAMs
    Kasper Green Larsen, Mark Simkin, Kevin Yeo
    TCC'20: 18th Conference on Theory of Cryptography.
  33. Secret Sharing Lower Bound: Either Reconstruction is Hard or Shares are Long
    Kasper Green Larsen, Mark Simkin
    SCN'20: 12th Conference on Security and Cryptography for Networks.
  34. Near-Tight Margin-Based Generalization Bounds for Support Vector Machines
    Allan Grønlund, Lior Kamma, Kasper Green Larsen
    ICML'20: 37th International Conference on Machine Learning.
  35. Optimal Learning of Joint Alignments with a Faulty Oracle
    Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis
    ISIT'20: IEEE International Symposium on Information Theory.
  36. Clustering with a Faulty Oracle
    Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis
    WWW'20: The Web Conference.
  37. Lower Bounds for Oblivious Near-Neighbor Search
    Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
    SODA'20: 31st ACM-SIAM Symposium on Discrete Algorithms.
  38. Margin-Based Generalization Lower Bounds for Boosted Classifiers
    Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson
    NeurIPS'19: 33rd Conference on Neural Information Processing Systems.
  39. Communication Lower Bounds for Statistically Secure MPC, with or without Preprocessing
    Ivan Damgård, Kasper Green Larsen, Jesper Buus Nielsen
    CRYPTO'19: 39th International Cryptology Conference.
  40. Optimal Minimal Margin Maximization with Boosting
    Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen
    ICML'19: 36th International Conference on Machine Learning.
  41. Lower Bounds for Multiplication via Network Coding
    Peyman Afshani, Casper Freksen, Lior Kamma, Kasper Green Larsen
    ICALP'19: 46th International Colloquium on Automata, Languages and Programming.
  42. Lower Bounds for External Memory Integer Sorting via Network Coding
    Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, Elaine Shi
    STOC'19: 51st ACM Symposium on Theory of Computing.
    Invited to Communications of the ACM.
  43. Constructive Discrepancy Minimization with Hereditary L2 Guarantees
    Kasper Green Larsen
    STACS'19: 36th Symposium on Theoretical Aspects of Computer Science.
  44. Lower Bounds for Oblivious Data Structures
    Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen
    SODA'19: 30th ACM-SIAM Symposium on Discrete Algorithms.
  45. A Faster External Memory Priority Queue with DecreaseKeys
    Shunhua Jiang, Kasper Green Larsen
    SODA'19: 30th ACM-SIAM Symposium on Discrete Algorithms.
  46. Fully Understanding the Hashing Trick
    Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen
    NeurIPS'18: 32nd Conference on Neural Information Processing Systems.
    Accepted as Spotlight paper.
  47. Yes, There is an Oblivious RAM Lower Bound!
    Kasper Green Larsen, Jesper Buus Nielsen
    CRYPTO'18: 38th International Cryptology Conference.
    Winner of the Best Paper Award.
  48. Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
    Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen
    STOC'18: 50th ACM Symposium on Theory of Computing.
  49. Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
    Kasper Green Larsen, Omri Weinstein, Huacheng Yu
    STOC'18: 50th ACM Symposium on Theory of Computing.
    Invited to special issue of SIAM Journal on Computing (SICOMP).
  50. Upper and Lower Bounds for Dynamic Data Structures on Strings
    Raphael Clifford, Allan Grønlund, Kasper Green Larsen, Tatiana Starikovskaya
    STACS'18: 35th Symposium on Theoretical Aspects of Computer Science.
  51. On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms
    Casper Benjamin Freksen, Kasper Green Larsen
    ISAAC'17: 28th International Symposium on Algorithms and Computation.
    Invited to special issue of Algorithmica.
  52. A Dichotomy for Regular Expression Membership Testing
    Karl Bringmann, Allan Grønlund, Kasper Green Larsen
    FOCS'17: 58th IEEE Symposium on Foundations of Computer Science.
  53. Optimality of the Johnson-Lindenstrauss Lemma
    Kasper Green Larsen, Jelani Nelson
    FOCS'17: 58th IEEE Symposium on Foundations of Computer Science.
    Invited to special issue of SIAM Journal on Computing (SICOMP). Declined
  54. DecreaseKeys are Expensive for External Memory Priority Queues
    Kasper Eenberg, Kasper Green Larsen, Huacheng Yu
    STOC'17: 49th ACM Symposium on Theory of Computing.
  55. Faster Online Matrix-Vector Multiplication
    Kasper Green Larsen, Ryan Williams
    SODA'17: 28th ACM-SIAM Symposium on Discrete Algorithms.
  56. 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.
  57. 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.
    Invited to Communications of the ACM.
  58. How to Prove Knowledge of Small Secrets
    Carsten Baum, Ivan Damgård, Kasper Green Larsen, Michael Nielsen
    CRYPTO'16: 36th International Cryptology Conference.
  59. 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.
  60. 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.
  61. 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.
  62. Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
    Joshua Brody, Kasper Green Larsen
    ToC: Theory of Computing. Vol 11, 2015.
  63. 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.
  64. 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.
  65. Optimal Planar Orthogonal Skyline Counting Queries
    Gerth Stølting Brodal, Kasper Green Larsen
    SWAT'14: 14th Scandinavian Symposium and Workshops on Algorithm Theory.
  66. 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.
  67. 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.
  68. Models and Techniques for Proving Data Structure Lower Bounds
    Kasper Green Larsen
    PhD Dissertation. Handed in February 28th, 2013. Successfully defended May 17th, 2013.
    Winner of the Aarhus University Ph.D. Prize.
  69. Succinct Sampling from Discrete Distributions
    Karl Bringmann, Kasper Green Larsen
    STOC'13: 45th ACM Symposium on Theory of Computing.
  70. 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.
  71. Near-Optimal Range Reporting Structures for Categorical Data
    Kasper Green Larsen, Freek van Walderveen
    SODA'13: 24th ACM-SIAM Symposium on Discrete Algorithms.
  72. I/O-Efficient Spatial Data Structures for Range Queries
    Lars Arge, Kasper Green Larsen
    Invited abstract in SIGSPATIAL Special, July, 2012.
  73. Higher Cell Probe Lower Bounds for Evaluating Polynomials
    Kasper Green Larsen
    FOCS'12: 53rd IEEE Symposium on Foundations of Computer Science.
  74. 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.
  75. 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.
  76. The Cell Probe Complexity of Dynamic Range Counting
    Kasper Green Larsen
    STOC'12: 44th ACM Symposium on Theory of Computing.
    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), declined.
  77. 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).
  78. 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.
  79. On Range Searching in the Group Model and Combinatorial Discrepancy
    Kasper Green Larsen
    FOCS'11: 52nd IEEE Symposium on Foundations of Computer Science.
    Winner of the Best Student Paper Award (the Machtey Award).
    Invited to special issue of SIAM Journal on Computing (SICOMP).
  80. 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.
  81. (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).
  82. 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.
  83. 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.
  84. 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.
  85. 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.
  86. 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.
  87. 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.