default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDKasper Green Larsen
Kasper Dalgaard Larsen
Person information
- affiliation: Aarhus University, Department of Computer Science, Denmark
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j13]Peyman Afshani, Rasmus Killmann, Kasper Green Larsen:
Hierarchical categories in colored searching. Comput. Geom. 121: 102090 (2024)- [j12]Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran:
Diagonalization Games. Am. Math. Mon. 131(10): 866-879 (2024) - [c85]Amin Karbasi, Kasper Green Larsen:
The Impossibility of Parallelizing Boosting. ALT 2024: 635-653 - [c84]Ishaq Aden-Ali, Mikael Møller Høandgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy:
Majority-of-Three: The Simplest Optimal Learner? COLT 2024: 22-45 - [c83]Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin:
Invertible Bloom Lookup Tables with Less Memory and Randomness. ESA 2024: 54:1-54:17 - [c82]Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy:
Revisiting Agnostic PAC Learning. FOCS 2024: 1968-1982 - [c81]Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano
, Toniann Pitassi, Kevin Yeo, Or Zamir:
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. ICALP 2024: 104:1-104:12 - [c80]Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, Chris Schwiegelshohn:
Sparse Dimensionality Reduction Revisited. ICML 2024 - [c79]Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, Felix Zhou:
Replicable Learning of Large-Margin Halfspaces. ICML 2024 - [c78]Kasper Green Larsen:
Bagging is an Optimal PAC Learner (Extended Abstract). IJCAI 2024: 8411-8415 - [c77]Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen:
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. ITCS 2024: 22:1-22:25 - [c76]Kasper Green Larsen:
From TCS to Learning Theory (Invited Paper). MFCS 2024: 4:1-4:9 - [c75]Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen:
Sublinear Time Shortest Path in Expander Graphs. MFCS 2024: 8:1-8:13 - [i81]Arthur da Cunha, Kasper Green Larsen, Martin Ritzert:
Boosting, Voting Classifiers and Randomized Sample Compression Schemes. CoRR abs/2402.02976 (2024) - [i80]Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, Felix Zhou:
Replicable Learning of Large-Margin Halfspaces. CoRR abs/2402.13857 (2024) - [i79]Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy:
Majority-of-Three: The Simplest Optimal Learner? CoRR abs/2403.08831 (2024) - [i78]Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy:
Revisiting Agnostic PAC Learning. CoRR abs/2407.19777 (2024) - [i77]Arthur da Cunha, Mikael Møller Høgsgaard, Kasper Green Larsen:
Optimal Parallelization of Boosting. CoRR abs/2408.16653 (2024) - [i76]Mikael Møller Høgsgaard, Kasper Green Larsen, Markus Engelund Mathiasen:
The Many Faces of Optimal Weak-to-Strong Learning. CoRR abs/2408.17148 (2024) - [i75]Karl Bringmann, Kasper Green Larsen, André Nusser, Eva Rotenberg, Yanheng Wang:
Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation. CoRR abs/2410.00996 (2024) - [i74]Allan Grønlund, Kasper Green Larsen:
An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning. CoRR abs/2411.02087 (2024) - 2023
- [c74]Kasper Green Larsen, Maciej Obremski, Mark Simkin:
Distributed Shuffling in Adversarial Environments. ITC 2023: 10:1-10:15 - [c73]Kasper Green Larsen:
Bagging is an Optimal PAC Learner. COLT 2023: 450-468 - [c72]Nils Fleischhacker, Kasper Green Larsen, Mark Simkin:
How to Compress Encrypted Data. EUROCRYPT (1) 2023: 551-577 - [c71]Kasper Green Larsen, Huacheng Yu:
Super-Logarithmic Lower Bounds for Dynamic Graph Problems. FOCS 2023: 1589-1604 - [c70]Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen:
The Fast Johnson-Lindenstrauss Transform Is Even Faster. ICML 2023: 9689-9715 - [c69]Mikael Møller Høgsgaard, Kasper Green Larsen, Martin Ritzert:
AdaBoost is not an Optimal Weak to Strong Learner. ICML 2023: 13118-13140 - [c68]Kasper Green Larsen:
Fast Discrepancy Minimization with Hereditary Guarantees. SODA 2023: 276-289 - [c67]Eldon Chung, Kasper Green Larsen:
Stronger 3SUM-Indexing Lower Bounds. SODA 2023: 444-455 - [c66]Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen:
Barriers for Faster Dimensionality Reduction. STACS 2023: 31:1-31:15 - [i73]Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran:
Diagonalization Games. CoRR abs/2301.01924 (2023) - [i72]Amin Karbasi, Kasper Green Larsen:
The Impossibility of Parallelizing Boosting. CoRR abs/2301.09627 (2023) - [i71]Mikael Møller Høgsgaard, Kasper Green Larsen, Martin Ritzert:
AdaBoost is not an Optimal Weak to Strong Learner. CoRR abs/2301.11571 (2023) - [i70]Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, Chris Schwiegelshohn:
Sparse Dimensionality Reduction Revisited. CoRR abs/2302.06165 (2023) - [i69]Kasper Green Larsen, Huacheng Yu:
Super-Logarithmic Lower Bounds for Dynamic Graph Problems. CoRR abs/2304.08745 (2023) - [i68]Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin:
Invertible Bloom Lookup Tables with Less Memory and Randomness. CoRR abs/2306.07583 (2023) - [i67]Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen:
Sublinear Time Shortest Path in Expander Graphs. CoRR abs/2307.06113 (2023) - [i66]Kasper Green Larsen, Rasmus Pagh, Toniann Pitassi, Or Zamir:
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. CoRR abs/2308.16042 (2023) - [i65]Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen:
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. CoRR abs/2311.10204 (2023) - [i64]Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran:
Diagonalization Games. Electron. Colloquium Comput. Complex. TR23 (2023) - [i63]Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin:
Invertible Bloom Lookup Tables with Less Memory and Randomness. IACR Cryptol. ePrint Arch. 2023: 918 (2023) - [i62]Nils Fleischhacker, Kasper Green Larsen, Mark Simkin:
Compressing Encrypted Data Over Small Fields. IACR Cryptol. ePrint Arch. 2023: 946 (2023) - 2022
- [c65]Yair Bartal, Ora Nova Fandina, Kasper Green Larsen:
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. SoCG 2022: 13:1-13:16 - [c64]Nils Fleischhacker, Kasper Green Larsen, Mark Simkin:
Property-Preserving Hash Functions for Hamming Distance from Standard Assumptions. EUROCRYPT (2) 2022: 764-781 - [c63]Peyman Afshani, Rasmus Killmann, Kasper Green Larsen:
Hierarchical Categories in Colored Searching. ISAAC 2022: 25:1-25:15 - [c62]Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar:
Improved Coresets for Euclidean k-Means. NeurIPS 2022 - [c61]Kasper Green Larsen, Martin Ritzert:
Optimal Weak to Strong Learning. NeurIPS 2022 - [c60]Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn:
Towards optimal lower bounds for k-median and k-means coresets. STOC 2022: 1038-1051 - [i61]Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn:
Towards Optimal Lower Bounds for k-median and k-means Coresets. CoRR abs/2202.12793 (2022) - [i60]Eldon Chung, Kasper Green Larsen:
Stronger 3SUM-Indexing Lower Bounds. CoRR abs/2203.09334 (2022) - [i59]Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen:
The Fast Johnson-Lindenstrauss Transform is Even Faster. CoRR abs/2204.01800 (2022) - [i58]Kasper Green Larsen, Martin Ritzert:
Optimal Weak to Strong Learning. CoRR abs/2206.01563 (2022) - [i57]Kasper Green Larsen:
Fast Discrepancy Minimization with Hereditary Guarantees. CoRR abs/2207.03268 (2022) - [i56]Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen:
Barriers for Faster Dimensionality Reduction. CoRR abs/2207.03304 (2022) - [i55]Peyman Afshani, Rasmus Killmann, Kasper Green Larsen:
Hierarchical Categories in Colored Searching. CoRR abs/2210.05403 (2022) - [i54]Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar:
Improved Coresets for Euclidean k-Means. CoRR abs/2211.08184 (2022) - [i53]Kasper Green Larsen:
Bagging is an Optimal PAC Learner. CoRR abs/2212.02264 (2022) - [i52]Kasper Green Larsen, Maciej Obremski, Mark Simkin:
Distributed Shuffling in Adversarial Environments. IACR Cryptol. ePrint Arch. 2022: 560 (2022) - [i51]Nils Fleischhacker, Kasper Green Larsen, Mark Simkin:
How to Compress Encrypted Data. IACR Cryptol. ePrint Arch. 2022: 1413 (2022) - 2021
- [c59]Ivan Bjerre Damgård, Kasper Green Larsen, Sophia Yakoubov:
Broadcast Secret-Sharing, Bounds and Applications. ITC 2021: 10:1-10:20 - [c58]Kasper Green Larsen, Rasmus Pagh, Jakub Tetek:
CountSketches, Feature Hashing and the Median of Three. ICML 2021: 6011-6020 - [c57]Zahra Jafargholi, Kasper Green Larsen, Mark Simkin:
Optimal Oblivious Priority Queues. SODA 2021: 2366-2383 - [c56]Kasper Green Larsen, Jonathan Lindegaard Starup, Jesper Steensgaard:
Further Unifying the Landscape of Cell Probe Lower Bounds. SOSA 2021: 224-231 - [i50]Kasper Green Larsen, Rasmus Pagh, Jakub Tetek:
CountSketches, Feature Hashing and the Median of Three. CoRR abs/2102.02193 (2021) - [i49]Nils Fleischhacker, Kasper Green Larsen, Mark Simkin:
Property-Preserving Hash Functions from Standard Assumptions. CoRR abs/2106.06453 (2021) - [i48]Yair Bartal, Ora Nova Fandina, Kasper Green Larsen:
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. CoRR abs/2107.06626 (2021) - [i47]Nils Fleischhacker, Kasper Green Larsen, Mark Simkin:
Property-Preserving Hash Functions from Standard Assumptions. IACR Cryptol. ePrint Arch. 2021: 793 (2021) - 2020
- [j11]Casper Benjamin Freksen, Kasper Green Larsen:
On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms. Algorithmica 82(2): 338-354 (2020) - [j10]Alireza Farhadi, Mohammad Taghi Hajiaghayi, Kasper Green Larsen, Elaine Shi:
Lower bounds for external memory integer sorting via network coding. Commun. ACM 63(10): 97-105 (2020) - [j9]Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. SIAM J. Comput. 49(5) (2020) - [c55]Allan Grønlund, Lior Kamma, Kasper Green Larsen:
Near-Tight Margin-Based Generalization Bounds for Support Vector Machines. ICML 2020: 3779-3788 - [c54]Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis:
Optimal Learning of Joint Alignments with a Faulty Oracle. ISIT 2020: 2492-2497 - [c53]Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis:
Optimal Learning of Joint Alignments with a Faulty Oracle. ITA 2020: 1-10 - [c52]Allan Grønlund, Lior Kamma, Kasper Green Larsen:
Margins are Insufficient for Explaining Gradient Boosting. NeurIPS 2020 - [c51]Kasper Green Larsen, Mark Simkin:
Secret Sharing Lower Bound: Either Reconstruction is Hard or Shares are Long. SCN 2020: 566-578 - [c50]Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo:
Lower Bounds for Oblivious Near-Neighbor Search. SODA 2020: 1116-1134 - [c49]Kasper Green Larsen, Mark Simkin, Kevin Yeo:
Lower Bounds for Multi-server Oblivious RAMs. TCC (1) 2020: 486-503 - [c48]Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis:
Clustering with a faulty oracle. WWW 2020: 2831-2834 - [i46]Allan Grønlund, Lior Kamma, Kasper Green Larsen:
Near-Tight Margin-Based Generalization Bounds for Support Vector Machines. CoRR abs/2006.02175 (2020) - [i45]Kasper Green Larsen, Jonathan Lindegaard Starup, Jesper Steensgaard:
Further Unifying the Landscape of Cell Probe Lower Bounds. CoRR abs/2008.05145 (2020) - [i44]Allan Grønlund, Lior Kamma, Kasper Green Larsen:
Margins are Insufficient for Explaining Gradient Boosting. CoRR abs/2011.04998 (2020)
2010 – 2019
- 2019
- [j8]Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup:
Heavy hitters via cluster-preserving clustering. Commun. ACM 62(8): 95-100 (2019) - [j7]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: 28-50 (2019) - [c47]Ivan Damgård, Kasper Green Larsen, Jesper Buus Nielsen:
Communication Lower Bounds for Statistically Secure MPC, With or Without Preprocessing. CRYPTO (2) 2019: 61-84 - [c46]Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen:
Lower Bounds for Multiplication via Network Coding. ICALP 2019: 10:1-10:12 - [c45]Alexander Mathiasen, Kasper Green Larsen, Allan Grønlund:
Optimal Minimal Margin Maximization with Boosting. ICML 2019: 4392-4401 - [c44]Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson:
Margin-Based Generalization Lower Bounds for Boosted Classifiers. NeurIPS 2019: 11940-11949 - [c43]Shunhua Jiang, Kasper Green Larsen:
A Faster External Memory Priority Queue with DecreaseKeys. SODA 2019: 1331-1343 - [c42]Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen:
Lower Bounds for Oblivious Data Structures. SODA 2019: 2439-2447 - [c41]Kasper Green Larsen:
Constructive Discrepancy Minimization with Hereditary L2 Guarantees. STACS 2019: 48:1-48:13 - [c40]Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, Elaine Shi:
Lower bounds for external memory integer sorting via network coding. STOC 2019: 997-1008 - [r1]Kasper Green Larsen:
Dimension Reduction. Encyclopedia of Big Data Technologies 2019 - [i43]Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen:
Optimal Minimal Margin Maximization with Boosting. CoRR abs/1901.10789 (2019) - [i42]Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen:
Lower Bounds for Multiplication via Network Coding. CoRR abs/1902.10935 (2019) - [i41]Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo:
Lower Bounds for Oblivious Near-Neighbor Search. CoRR abs/1904.04828 (2019) - [i40]Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis:
Optimal Learning of Joint Alignments with a Faulty Oracle. CoRR abs/1909.09912 (2019) - [i39]Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson:
Margin-Based Generalization Lower Bounds for Boosted Classifiers. CoRR abs/1909.12518 (2019) - [i38]Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo:
Lower Bounds for Oblivious Near-Neighbor Search. Electron. Colloquium Comput. Complex. TR19 (2019) - [i37]Kasper Green Larsen, Mark Simkin:
Exponential Lower Bounds for Secret Sharing. IACR Cryptol. ePrint Arch. 2019: 174 (2019) - [i36]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: 220 (2019) - [i35]Zahra Jafargholi, Kasper Green Larsen, Mark Simkin:
Optimal Oblivious Priority Queues and Offline Oblivious RAM. IACR Cryptol. ePrint Arch. 2019: 237 (2019) - [i34]Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo:
Lower Bounds for Oblivious Near-Neighbor Search. IACR Cryptol. ePrint Arch. 2019: 377 (2019) - [i33]Kasper Green Larsen, Mark Simkin, Kevin Yeo:
Lower Bounds for Multi-Server Oblivious RAMs. IACR Cryptol. ePrint Arch. 2019: 1108 (2019) - 2018
- [c39]Kasper Green Larsen, Jesper Buus Nielsen:
Yes, There is an Oblivious RAM Lower Bound! CRYPTO (2) 2018: 523-542 - [c38]Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. ITA 2018: 1-40 - [c37]Lior Kamma, Casper Benjamin Freksen, Kasper Green Larsen:
Fully Understanding The Hashing Trick. NeurIPS 2018: 5394-5404 - [c36]Raphaël Clifford, Allan Grønlund, Kasper Green Larsen, Tatiana Starikovskaya:
Upper and Lower Bounds for Dynamic Data Structures on Strings. STACS 2018: 22:1-22:14 - [c35]Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds. STOC 2018: 978-989 - [c34]Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen:
Tight cell probe bounds for succinct Boolean matrix-vector multiplication. STOC 2018: 1297-1306 - [i32]Raphaël Clifford, Allan Grønlund, Kasper Green Larsen, Tatiana Starikovskaya:
Upper and lower bounds for dynamic data structures on strings. CoRR abs/1802.06545 (2018) - [i31]Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen:
Fully Understanding the Hashing Trick. CoRR abs/1805.08539 (2018) - [i30]Shunhua Jiang, Kasper Green Larsen:
A Faster External Memory Priority Queue with DecreaseKeys. CoRR abs/1806.07598 (2018) - [i29]Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen:
Lower Bounds for Oblivious Data Structures. CoRR abs/1810.10635 (2018) - [i28]Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, Elaine Shi:
Lower Bounds for External Memory Integer Sorting via Network Coding. CoRR abs/1811.01313 (2018) - [i27]Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, Kurt Mehlhorn:
The Query Complexity of a Permutation-Based Variant of Mastermind. CoRR abs/1812.08480 (2018) - [i26]Kasper Green Larsen, Jesper Buus Nielsen:
Yes, There is an Oblivious RAM Lower Bound! Electron. Colloquium Comput. Complex. TR18 (2018) - [i25]Kasper Green Larsen, Jesper Buus Nielsen:
Yes, There is an Oblivious RAM Lower Bound! IACR Cryptol. ePrint Arch. 2018: 423 (2018) - 2017
- [c33]Karl Bringmann, Allan Grønlund, Kasper Green Larsen:
A Dichotomy for Regular Expression Membership Testing. FOCS 2017: 307-318 - [c32]Kasper Green Larsen, Jelani Nelson:
Optimality of the Johnson-Lindenstrauss Lemma. FOCS 2017: 633-638 - [c31]Casper Benjamin Freksen, Kasper Green Larsen:
On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms. ISAAC 2017: 32:1-32:12 - [c30]Kasper Green Larsen, R. Ryan Williams:
Faster Online Matrix-Vector Multiplication. SODA 2017: 2182-2189 - [c29]Kasper Eenberg, Kasper Green Larsen, Huacheng Yu:
DecreaseKeys are expensive for external memory priority queues. STOC 2017: 1081-1093 - [i24]Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen:
Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D. CoRR abs/1701.07204 (2017) - [i23]Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. CoRR abs/1703.03575 (2017) - [i22]