![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
Kasper Green Larsen
Person information
- affiliation: Aarhus University, Department of Computer Science, Denmark
Refine list
![note](https://dblp.dagstuhl.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [j12]Peyman Afshani, Rasmus Killmann, Kasper Green Larsen:
Hierarchical categories in colored searching. Comput. Geom. 121: 102090 (2024) - [c80]Amin Karbasi, Kasper Green Larsen:
The Impossibility of Parallelizing Boosting. ALT 2024: 635-653 - [c79]Ishaq Aden-Ali, Mikael Møller Høandgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy:
Majority-of-Three: The Simplest Optimal Learner? COLT 2024: 22-45 - [c78]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 - [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 - [i77]Arthur da Cunha, Kasper Green Larsen, Martin Ritzert:
Boosting, Voting Classifiers and Randomized Sample Compression Schemes. CoRR abs/2402.02976 (2024) - [i76]Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, Felix Zhou:
Replicable Learning of Large-Margin Halfspaces. CoRR abs/2402.13857 (2024) - [i75]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) - [i74]Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy:
Revisiting Agnostic PAC Learning. CoRR abs/2407.19777 (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]Casper Benjamin Freksen, Kasper Green Larsen:
On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms. CoRR abs/1706.10110 (2017) - [i21]Kasper Green Larsen:
Constructive Discrepancy Minimization with Hereditary L2 Guarantees. CoRR abs/1711.02860 (2017) - [i20]Diptarka Chakraborty
, Lior Kamma, Kasper Green Larsen:
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication. CoRR abs/1711.04467 (2017) - [i19]Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [c28]Carsten Baum, Ivan Damgård, Kasper Green Larsen, Michael Nielsen:
How to Prove Knowledge of Small Secrets. CRYPTO (3) 2016: 478-498 - [c27]Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup
:
Heavy Hitters via Cluster-Preserving Clustering. FOCS 2016: 61-70 - [c26]Kasper Green Larsen, Jelani Nelson:
The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. ICALP 2016: 82:1-82:11 - [c25]Allan Grønlund, Kasper Green Larsen:
Towards Tight Lower Bounds for Range Reporting on the RAM. ICALP 2016: 92:1-92:12 - [i18]Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup:
Heavy hitters via cluster-preserving clustering. CoRR abs/1604.01357 (2016) - [i17]Kasper Green Larsen, Ryan Williams:
Faster Online Matrix-Vector Multiplication. CoRR abs/1605.01695 (2016) - [i16]Kasper Green Larsen, Jelani Nelson:
Optimality of the Johnson-Lindenstrauss Lemma. CoRR abs/1609.02094 (2016) - [i15]Kasper Eenberg, Kasper Green Larsen, Huacheng Yu:
DecreaseKeys are Expensive for External Memory Priority Queues. CoRR abs/1611.00911 (2016) - [i14]Karl Bringmann, Allan Grønlund, Kasper Green Larsen:
A Dichotomy for Regular Expression Membership Testing. CoRR abs/1611.00918 (2016) - [i13]Carsten Baum, Ivan Damgård, Kasper Green Larsen, Michael Nielsen:
How to prove knowledge of small secrets. IACR Cryptol. ePrint Arch. 2016: 538 (2016) - 2015
- [j6]Kasper Green Larsen, J. Ian Munro, Jesper Sindahl Nielsen, Sharma V. Thankachan
:
On hardness of several string indexing problems. Theor. Comput. Sci. 582: 74-82 (2015) - [j5]Joshua Brody, Kasper Green Larsen:
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures. Theory Comput. 11: 471-489 (2015) - [c24]Raphaël Clifford, Allan Grønlund, Kasper Green Larsen:
New Unconditional Hardness Results for Dynamic and Online Problems. FOCS 2015: 1089-1107 - [c23]Mayank Goswami, Allan Grønlund Jørgensen, Kasper Green Larsen, Rasmus Pagh
:
Approximate Range Emptiness in Constant Time and Optimal Space. SODA 2015: 769-775 - [c22]Kasper Green Larsen, Jelani Nelson, Huy L. Nguyên:
Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms. STOC 2015: 803-812 - [i12]Raphaël Clifford, Allan Grønlund Jørgensen, Kasper Green Larsen:
New Unconditional Hardness Results for Dynamic and Online Problems. CoRR abs/1504.01836 (2015) - 2014
- [j4]Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison
, Bryan T. Wilkinson:
Linear-Space Data Structures for Range Mode Query in Arrays. Theory Comput. Syst. 55(4): 719-741 (2014) - [j3]Kasper Green Larsen:
On Range Searching in the Group Model and Combinatorial Discrepancy. SIAM J. Comput. 43(2): 673-686 (2014) - [c21]Kasper Green Larsen, J. Ian Munro, Jesper Sindahl Nielsen, Sharma V. Thankachan:
On Hardness of Several String Indexing Problems. CPM 2014: 242-251 - [c20]Stephen Alstrup, Esben Bistrup Halvorsen, Kasper Green Larsen:
Near-optimal labeling schemes for nearest common ancestors. SODA 2014: 972-982 - [c19]Gerth Stølting Brodal
, Kasper Green Larsen:
Optimal Planar Orthogonal Skyline Counting Queries. SWAT 2014: 110-121 - [i11]Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen:
Time lower bounds for nonadaptive turnstile streaming algorithms. CoRR abs/1407.2151 (2014) - [i10]Mayank Goswami, Allan Grønlund Jørgensen, Kasper Green Larsen, Rasmus Pagh:
Approximate Range Emptiness in Constant Time and Optimal Space. CoRR abs/1407.2907 (2014) - [i9]Allan Grønlund Jørgensen, Kasper Green Larsen:
Towards Tight Lower Bounds for Range Reporting on the RAM. CoRR abs/1411.0644 (2014) - [i8]Kasper Green Larsen, Jelani Nelson:
The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction. CoRR abs/1411.2404 (2014) - 2013
- [j2]Peyman Afshani, Pankaj K. Agarwal, Lars Arge, Kasper Green Larsen, Jeff M. Phillips:
(Approximate) Uncertain Skylines. Theory Comput. Syst. 52(3): 342-366 (2013) - [c18]Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, Kurt Mehlhorn:
The Query Complexity of Finding a Hidden Permutation. Space-Efficient Data Structures, Streams, and Algorithms 2013: 1-11 - [c17]Kasper Green Larsen, Freek van Walderveen:
Near-Optimal Range Reporting Structures for Categorical Data. SODA 2013: 265-276 - [c16]Karl Bringmann, Kasper Green Larsen:
Succinct sampling from discrete distributions. STOC 2013: 775-782 - [i7]Gerth Stølting Brodal, Kasper Green Larsen:
Optimal Planar Orthogonal Skyline Counting Queries. CoRR abs/1304.7959 (2013) - [i6]Stephen Alstrup, Esben Bistrup Halvorsen, Kasper Green Larsen:
Near-optimal labeling schemes for nearest common ancestors. CoRR abs/1312.4413 (2013) - 2012
- [j1]Lars Arge, Kasper Green Larsen:
I/O-efficient spatial data structures for range queries. ACM SIGSPATIAL Special 4(2): 2-7 (2012) - [c15]Kasper Green Larsen, Huy Le Nguyen:
Improved range searching lower bounds. SCG 2012: 171-178 - [c14]Peyman Afshani, Lars Arge, Kasper Green Larsen:
Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model. SCG 2012: 323-332 - [c13]Kasper Green Larsen:
Higher Cell Probe Lower Bounds for Evaluating Polynomials. FOCS 2012: 293-301 - [c12]Kasper Green Larsen, Rasmus Pagh:
I/O-efficient data structures for colored range and prefix reporting. SODA 2012: 583-592 - [c11]Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison
, Bryan T. Wilkinson:
Linear-Space Data Structures for Range Mode Query in Arrays. STACS 2012: 290-301 - [c10]Kasper Green Larsen:
The cell probe complexity of dynamic range counting. STOC 2012: 85-94 - [i5]Joshua Brody, Kasper Green Larsen:
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures. CoRR abs/1208.2846 (2012) - [i4]Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Winzen, Kasper Green Larsen, Kurt Mehlhorn:
The Deterministic and Randomized Query Complexity of a Simple Guessing Game. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [c9]Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu:
Orthogonal range searching on the RAM, revisited. SCG 2011: 1-10 - [c8]Kasper Green Larsen:
On Range Searching in the Group Model and Combinatorial Discrepancy. FOCS 2011: 542-549 - [c7]Peyman Afshani, Pankaj K. Agarwal, Lars Arge, Kasper Green Larsen, Jeff M. Phillips:
(Approximate) uncertain skylines. ICDT 2011: 186-196 - [c6]Allan Grønlund Jørgensen, Kasper Green Larsen:
Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures. SODA 2011: 805-813 - [i3]Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu:
Orthogonal Range Searching on the RAM, Revisited. CoRR abs/1103.5510 (2011) - [i2]Kasper Green Larsen, Rasmus Pagh:
I/O-Efficient Data Structures for Colored Range and Prefix Reporting. CoRR abs/1104.3084 (2011) - [i1]Kasper Green Larsen:
The Cell Probe Complexity of Dynamic Range Counting. CoRR abs/1105.5933 (2011) - 2010
- [c5]Peyman Afshani, Lars Arge, Kasper Dalgaard Larsen:
Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements. SCG 2010: 240-246 - [c4]Lars Arge, Kasper Green Larsen, Thomas Mølhave, Freek van Walderveen:
Cleaning massive sonar point clouds. GIS 2010: 152-161 - [c3]Mark Greve, Allan Grønlund Jørgensen, Kasper Dalgaard Larsen, Jakob Truelsen:
Cell Probe Lower Bounds and Approximations for Range Mode. ICALP (1) 2010: 605-616
2000 – 2009
- 2009
- [c2]Peyman Afshani, Lars Arge, Kasper Dalgaard Larsen:
Orthogonal Range Reporting in Three and Higher Dimensions. FOCS 2009: 149-158 - 2007
- [c1]Michael E. Caspersen, Kasper Dalgaard Larsen, Jens Bennedsen:
Mental models and programming aptitude. ITiCSE 2007: 206-210
Coauthor Index
aka: Allan Grønlund
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-27 22:00 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint