Kasper Green Larsen

ORCID

Publication Activity (10 Years)

Years Active: 2010-2024
Publications (10 Years): 128

Top Venues

CoRR

IACR Cryptol. ePrint Arch.

SODA

STOC

Publications

Amin Karbasi, Kasper Green Larsen
The Impossibility of Parallelizing Boosting. ALT (2024)
Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. ITCS (2024)
Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy
Majority-of-Three: The Simplest Optimal Learner? CoRR (2024)
Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy
Revisiting Agnostic PAC Learning. CoRR (2024)
Kasper Green Larsen
From TCS to Learning Theory (Invited Paper). MFCS (2024)
Arthur da Cunha, Kasper Green Larsen, Martin Ritzert
Boosting, Voting Classifiers and Randomized Sample Compression Schemes. CoRR (2024)
Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo, Or Zamir
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. ICALP (2024)
Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, Felix Zhou
Replicable Learning of Large-Margin Halfspaces. CoRR (2024)
Ishaq Aden-Ali, Mikael Møller Høandgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy
Majority-of-Three: The Simplest Optimal Learner? COLT (2024)
Peyman Afshani, Rasmus Killmann, Kasper Green Larsen
Hierarchical categories in colored searching. Comput. Geom. 121 (2024)
Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen
Sublinear Time Shortest Path in Expander Graphs. MFCS (2024)
Amin Karbasi, Kasper Green Larsen
The Impossibility of Parallelizing Boosting. CoRR (2023)
Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran
Diagonalization Games. Electron. Colloquium Comput. Complex. (2023)
Kasper Green Larsen, Huacheng Yu
Super-Logarithmic Lower Bounds for Dynamic Graph Problems. FOCS (2023)
Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin
Invertible Bloom Lookup Tables with Less Memory and Randomness. CoRR (2023)
Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin
Invertible Bloom Lookup Tables with Less Memory and Randomness. IACR Cryptol. ePrint Arch. 2023 (2023)
Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
The Fast Johnson-Lindenstrauss Transform Is Even Faster. ICML (2023)
Kasper Green Larsen
Fast Discrepancy Minimization with Hereditary Guarantees. SODA (2023)
Kasper Green Larsen, Huacheng Yu
Super-Logarithmic Lower Bounds for Dynamic Graph Problems. CoRR (2023)
Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen
Sublinear Time Shortest Path in Expander Graphs. CoRR (2023)
Mikael Møller Høgsgaard, Kasper Green Larsen, Martin Ritzert
AdaBoost is not an Optimal Weak to Strong Learner. ICML (2023)
Eldon Chung, Kasper Green Larsen
Stronger 3SUM-Indexing Lower Bounds. SODA (2023)
Kasper Green Larsen, Rasmus Pagh, Toniann Pitassi, Or Zamir
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. CoRR (2023)
Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
Barriers for Faster Dimensionality Reduction. STACS (2023)
Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. CoRR (2023)
Kasper Green Larsen
Bagging is an Optimal PAC Learner. COLT (2023)
Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
Compressing Encrypted Data Over Small Fields. IACR Cryptol. ePrint Arch. 2023 (2023)
Kasper Green Larsen, Maciej Obremski, Mark Simkin
Distributed Shuffling in Adversarial Environments. ITC (2023)
Mikael Møller Høgsgaard, Kasper Green Larsen, Martin Ritzert
AdaBoost is not an Optimal Weak to Strong Learner. CoRR (2023)
Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, Chris Schwiegelshohn
Sparse Dimensionality Reduction Revisited. CoRR (2023)
Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran
Diagonalization Games. CoRR (2023)
Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
How to Compress Encrypted Data. EUROCRYPT (1) (2023)
Kasper Green Larsen, Martin Ritzert
Optimal Weak to Strong Learning. CoRR (2022)
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn
Towards optimal lower bounds for k-median and k-means coresets. STOC (2022)
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar
Improved Coresets for Euclidean k-Means. NeurIPS (2022)
Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
The Fast Johnson-Lindenstrauss Transform is Even Faster. CoRR (2022)
Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
Property-Preserving Hash Functions for Hamming Distance from Standard Assumptions. EUROCRYPT (2) (2022)
Kasper Green Larsen, Martin Ritzert
Optimal Weak to Strong Learning. NeurIPS (2022)
Peyman Afshani, Rasmus Killmann, Kasper Green Larsen
Hierarchical Categories in Colored Searching. CoRR (2022)
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn
Towards Optimal Lower Bounds for k-median and k-means Coresets. CoRR (2022)
Kasper Green Larsen
Fast Discrepancy Minimization with Hereditary Guarantees. CoRR (2022)
Yair Bartal, Ora Nova Fandina, Kasper Green Larsen
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. SoCG (2022)
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar
Improved Coresets for Euclidean k-Means. CoRR (2022)
Peyman Afshani, Rasmus Killmann, Kasper Green Larsen
Hierarchical Categories in Colored Searching. ISAAC (2022)
Kasper Green Larsen
Bagging is an Optimal PAC Learner. CoRR (2022)
Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
How to Compress Encrypted Data. IACR Cryptol. ePrint Arch. 2022 (2022)
Kasper Green Larsen, Maciej Obremski, Mark Simkin
Distributed Shuffling in Adversarial Environments. IACR Cryptol. ePrint Arch. 2022 (2022)
Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
Barriers for Faster Dimensionality Reduction. CoRR (2022)
Eldon Chung, Kasper Green Larsen
Stronger 3SUM-Indexing Lower Bounds. CoRR (2022)
Kasper Green Larsen, Rasmus Pagh, Jakub Tetek
CountSketches, Feature Hashing and the Median of Three. ICML (2021)
Allan Grønlund, Mikael Høgsgaard, Lior Kamma, Kasper Green Larsen
Compression Implies Generalization. CoRR (2021)
Zahra Jafargholi, Kasper Green Larsen, Mark Simkin
Optimal Oblivious Priority Queues. SODA (2021)
Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
Property-Preserving Hash Functions from Standard Assumptions. CoRR (2021)
Kasper Green Larsen, Rasmus Pagh, Jakub Tetek
CountSketches, Feature Hashing and the Median of Three. CoRR (2021)
Ivan Bjerre Damgård, Kasper Green Larsen, Sophia Yakoubov
Broadcast Secret-Sharing, Bounds and Applications. ITC (2021)
Kasper Green Larsen, Jonathan Lindegaard Starup, Jesper Steensgaard
Further Unifying the Landscape of Cell Probe Lower Bounds. SOSA (2021)
Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
Property-Preserving Hash Functions from Standard Assumptions. IACR Cryptol. ePrint Arch. 2021 (2021)
Yair Bartal, Ora Nova Fandina, Kasper Green Larsen
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. CoRR (2021)
Alireza Farhadi, Mohammad Taghi Hajiaghayi, Kasper Green Larsen, Elaine Shi
Lower bounds for external memory integer sorting via network coding. Commun. ACM 63 (10) (2020)
Kasper Green Larsen, Jonathan Lindegaard Starup, Jesper Steensgaard
Further Unifying the Landscape of Cell Probe Lower Bounds. CoRR (2020)
Kasper Green Larsen, Mark Simkin
Secret Sharing Lower Bound: Either Reconstruction is Hard or Shares are Long. SCN (2020)
Allan Grønlund, Lior Kamma, Kasper Green Larsen
Margins are Insufficient for Explaining Gradient Boosting. CoRR (2020)
Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis
Optimal Learning of Joint Alignments with a Faulty Oracle. ISIT (2020)
Allan Grønlund, Lior Kamma, Kasper Green Larsen
Margins are Insufficient for Explaining Gradient Boosting. NeurIPS (2020)
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. SIAM J. Comput. 49 (5) (2020)
Allan Grønlund, Lior Kamma, Kasper Green Larsen
Near-Tight Margin-Based Generalization Bounds for Support Vector Machines. CoRR (2020)
Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis
Optimal Learning of Joint Alignments with a Faulty Oracle. ITA (2020)
Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis
Clustering with a faulty oracle. WWW (2020)
Kasper Green Larsen, Mark Simkin, Kevin Yeo
Lower Bounds for Multi-server Oblivious RAMs. TCC (1) (2020)
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
Lower Bounds for Oblivious Near-Neighbor Search. SODA (2020)
Casper Benjamin Freksen, Kasper Green Larsen
On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms. Algorithmica 82 (2) (2020)
Allan Grønlund, Lior Kamma, Kasper Green Larsen
Near-Tight Margin-Based Generalization Bounds for Support Vector Machines. ICML (2020)
Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson
Margin-Based Generalization Lower Bounds for Boosted Classifiers. NeurIPS (2019)
Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen
Optimal Minimal Margin Maximization with Boosting. CoRR (2019)
Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen
Lower Bounds for Multiplication via Network Coding. CoRR (2019)
Kasper Green Larsen, Mark Simkin
Exponential Lower Bounds for Secret Sharing. IACR Cryptol. ePrint Arch. 2019 (2019)
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
Lower Bounds for Oblivious Near-Neighbor Search. CoRR (2019)
Kasper Green Larsen, Mark Simkin, Kevin Yeo
Lower Bounds for Multi-Server Oblivious RAMs. IACR Cryptol. ePrint Arch. 2019 (2019)
Shunhua Jiang, Kasper Green Larsen
A Faster External Memory Priority Queue with DecreaseKeys. SODA (2019)
Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, Kurt Mehlhorn
The query complexity of a permutation-based variant of Mastermind. Discret. Appl. Math. 260 (2019)
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup
Heavy hitters via cluster-preserving clustering. Commun. ACM 62 (8) (2019)
Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen
Lower Bounds for Oblivious Data Structures. SODA (2019)
Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen
Lower Bounds for Multiplication via Network Coding. ICALP (2019)
Ivan Damgård, Kasper Green Larsen, Jesper Buus Nielsen
Communication Lower Bounds for Statistically Secure MPC, with or without Preprocessing. IACR Cryptol. ePrint Arch. 2019 (2019)
Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis
Optimal Learning of Joint Alignments with a Faulty Oracle. CoRR (2019)
Ivan Damgård, Kasper Green Larsen, Jesper Buus Nielsen
Communication Lower Bounds for Statistically Secure MPC, With or Without Preprocessing. CRYPTO (2) (2019)
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
Lower Bounds for Oblivious Near-Neighbor Search. Electron. Colloquium Comput. Complex. 26 (2019)
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
Lower Bounds for Oblivious Near-Neighbor Search. IACR Cryptol. ePrint Arch. 2019 (2019)
Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson
Margin-Based Generalization Lower Bounds for Boosted Classifiers. CoRR (2019)
Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, Elaine Shi
Lower bounds for external memory integer sorting via network coding. STOC (2019)
Alexander Mathiasen, Kasper Green Larsen, Allan Grønlund
Optimal Minimal Margin Maximization with Boosting. ICML (2019)
Kasper Green Larsen
Constructive Discrepancy Minimization with Hereditary L2 Guarantees. STACS (2019)
Zahra Jafargholi, Kasper Green Larsen, Mark Simkin
Optimal Oblivious Priority Queues and Offline Oblivious RAM. IACR Cryptol. ePrint Arch. 2019 (2019)
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds. STOC (2018)
Kasper Green Larsen, Jesper Buus Nielsen
Yes, There is an Oblivious RAM Lower Bound! IACR Cryptol. ePrint Arch. 2018 (2018)
Kasper Green Larsen, Omri Weinstein, Huacheng Yu
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. ITA (2018)
Lior Kamma, Casper Benjamin Freksen, Kasper Green Larsen
Fully Understanding The Hashing Trick. NeurIPS (2018)
Shunhua Jiang, Kasper Green Larsen
A Faster External Memory Priority Queue with DecreaseKeys. CoRR (2018)
Raphaël Clifford, Allan Grønlund, Kasper Green Larsen, Tatiana Starikovskaya
Upper and lower bounds for dynamic data structures on strings. CoRR (2018)
Kasper Green Larsen, Jesper Buus Nielsen
Yes, There is an Oblivious RAM Lower Bound! Electron. Colloquium Comput. Complex. 25 (2018)

Kasper Green Larsen.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Kasper Green Larsen