Photo: Tariq
Mikkel Khan |
Kasper Green Larsen Professor, Ph.D. Department of Computer Science Aarhus University Contact Information Mail: larsen@cs.au.dk |
Boosting, Voting Classifiers and Randomized Sample Compression Schemes
Arthur da Cunha, Kasper Green Larsen, Martin Ritzert Manuscript. |
Sublinear Time Shortest Path in Expander Graphs
Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen Manuscript. |
Invertible Bloom Lookup Tables with Less Memory and Randomness
Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin Manuscript. |
Majority-of-Three: The Simplest Optimal Learner?
Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy COLT'24: 37th Conference on Learning Theory. |
Replicable Learning of Large-Margin Halfspaces
Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, Felix Zhou ICML'24: 41st International Conference on Machine Learning. Accepted as Spotlight paper. |
Sparse Dimensionality Reduction Revisited
Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, Chris Schwiegelshohn ICML'24: 41st International Conference on Machine Learning. |
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo, Or Zamir ICALP'24: 51st International Colloquium on Automata, Languages and Programming. |
The Impossibility of Parallelizing Boosting
Amin Karbasi, Kasper Green Larsen ALT'24: 35th Conference on Algorithmic Learning Theory. |
Diagonalization Games
Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran AMM'24: American Mathematical Monthly. Expected to appear in 2024. |
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. |
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). |
Bagging is an Optimal PAC Learner
Kasper Green Larsen COLT'23: 36th Conference on Learning Theory. Winner of the Best Paper Award. Invited to IJCAI'24 Sister Conferences Best Paper Track. Invited to HALG'24 (Highlights of Algorithms). |
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. |
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. |
Distributed Shuffling in Adversarial Environments
Kasper Green Larsen, Maciej Obremski, Mark Simkin ITC'23: 4th Information-Theoretic Cryptography Conference. |
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. |
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. |
Fast Discrepancy Minimization with Hereditary Guarantees
Kasper Green Larsen SODA'23: 34th ACM-SIAM Symposium on Discrete Algorithms. |
Stronger 3SUM-Indexing Lower Bounds
Eldon Chung, Kasper Green Larsen SODA'23: 34th ACM-SIAM Symposium on Discrete Algorithms. |
Optimal Weak to Strong Learning
Kasper Green Larsen, Martin Ritzert NeurIPS'22: 36th Conference on Neural Information Processing Systems. |
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. |
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). |
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. |
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 |
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. |
CountSketches, Feature Hashing and the Median of Three
Kasper Green Larsen, Rasmus Pagh, Jakub Tětek ICML'21: 38th International Conference on Machine Learning. |
Broadcast Secret-Sharing, Bounds and Applications
Ivan Damgård, Kasper Green Larsen, Sophia Yakoubov ITC'21: 2nd Information-Theoretic Cryptography Conference. |
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. |
Optimal Oblivious Priority Queues
Zahra Jafargholi, Kasper Green Larsen, Mark Simkin SODA'21: 32nd ACM-SIAM Symposium on Discrete Algorithms. |
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. |
Margins are Insufficient for Explaining Gradient Boosting
Allan Grønlund, Lior Kamma, Kasper Green Larsen NeurIPS'20: 34th Conference on Neural Information Processing Systems. |
Lower Bounds for Multi-Server Oblivious RAMs
Kasper Green Larsen, Mark Simkin, Kevin Yeo TCC'20: 18th Conference on Theory of Cryptography. |
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. |
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. |
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. |
Clustering with a Faulty Oracle
Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis WWW'20: The Web Conference. |
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. |
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. |
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. |
Optimal Minimal Margin Maximization with Boosting
Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen ICML'19: 36th International Conference on Machine Learning. |
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. |
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. |
Constructive Discrepancy Minimization with Hereditary L2 Guarantees
Kasper Green Larsen STACS'19: 36th Symposium on Theoretical Aspects of Computer Science. |
Lower Bounds for Oblivious Data Structures
Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen SODA'19: 30th ACM-SIAM Symposium on Discrete Algorithms. |
A Faster External Memory Priority Queue with DecreaseKeys
Shunhua Jiang, Kasper Green Larsen SODA'19: 30th ACM-SIAM Symposium on Discrete Algorithms. |
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. |
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. |
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. |
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). |
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. |
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. |
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. |
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 |
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. |
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. |
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. |
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. |
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. 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. 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. |
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. 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. |