Kasper Green Larsen

196 papers A* 55A 9B 9Misc 3Journal 105Unranked 14

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Learning with Monotone Adversarial Corruptions. CoRR Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty
2026	A*	`ed.`	Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026 SODA Kasper Green Larsen, Barna Saha
2026	J	`jnl`	The Sample Complexity of Replicable Realizable PAC Learning. CoRR Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, Clement Svendsen
2025	B	`conf`	A New Lower Bound for Multicolor Discrepancy with Applications to Fair Division. SAGT Ioannis Caragiannis, Kasper Green Larsen, Sudarshan Shyam
2025	J	`jnl`	A new lower bound for multi-color discrepancy with applications to fair division. CoRR Ioannis Caragiannis, Kasper Green Larsen, Sudarshan Shyam
2025	J	`jnl`	Actively Learning Halfspaces without Synthetic Data. CoRR Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha, Geelon So
2025	A*	`conf`	Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation. SoCG Karl Bringmann, Kasper Green Larsen, André Nusser, Eva Rotenberg, Yanheng Wang
2025	B	`conf`	Boosting, Voting Classifiers and Randomized Sample Compression Schemes. ALT Arthur da Cunha, Kasper Green Larsen, Martin Ritzert
2025	A*	`conf`	Improved Margin Generalization Bounds for Voting Classifiers. COLT Mikael Møller Høgsgaard, Kasper Green Larsen
2025	J	`jnl`	Improved Margin Generalization Bounds for Voting Classifiers. CoRR Mikael Møller Høgsgaard, Kasper Green Larsen
2025	J	`jnl`	Improved Replicable Boosting with Majority-of-Majorities. CoRR Kasper Green Larsen, Markus Engelund Mathiasen, Clement Svendsen
2025	J	`jnl`	Tight Generalization Bounds for Large-Margin Halfspaces. CoRR Kasper Green Larsen, Natascha Schalburg
2025	J	`jnl`	Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets. CoRR Kasper Green Larsen, Natascha Schalburg
2025	—	`conf`	Time/Space Tradeoffs for Generic Attacks on Delay Functions. TCC (4) Kasper Green Larsen, Mark Simkin
2024	J	`jnl`	An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning. CoRR Allan Grønlund, Kasper Green Larsen
2024	J	`jnl`	Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation. CoRR Karl Bringmann, Kasper Green Larsen, André Nusser, Eva Rotenberg, Yanheng Wang
2024	A*	`conf`	Bagging is an Optimal PAC Learner (Extended Abstract). IJCAI Kasper Green Larsen
2024	J	`jnl`	Boosting, Voting Classifiers and Randomized Sample Compression Schemes. CoRR Arthur da Cunha, Kasper Green Larsen, Martin Ritzert
2024	A*	`conf`	Derandomizing Multi-Distribution Learning. NeurIPS Kasper Green Larsen, Omar Montasser, Nikita Zhivotovskiy
2024	J	`jnl`	Derandomizing Multi-Distribution Learning. CoRR Kasper Green Larsen, Omar Montasser, Nikita Zhivotovskiy
2024	J	`jnl`	Diagonalization Games. Am. Math. Mon. Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran
2024	B	`conf`	From TCS to Learning Theory (Invited Paper). MFCS Kasper Green Larsen
2024	J	`jnl`	Hierarchical categories in colored searching. Comput. Geom. Peyman Afshani, Rasmus Killmann, Kasper Green Larsen
2024	A	`conf`	Invertible Bloom Lookup Tables with Less Memory and Randomness. ESA Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin
2024	A*	`conf`	Majority-of-Three: The Simplest Optimal Learner? COLT Ishaq Aden-Ali, Mikael Møller Høandgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy
2024	J	`jnl`	Majority-of-Three: The Simplest Optimal Learner? CoRR Ishaq Aden-Ali, Mikael Møller Høgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy
2024	A*	`conf`	Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. ICALP Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo, Or Zamir
2024	A*	`conf`	Optimal Parallelization of Boosting. NeurIPS Arthur da Cunha, Mikael Møller Høgsgaard, Kasper Green Larsen
2024	J	`jnl`	Optimal Parallelization of Boosting. CoRR Arthur da Cunha, Mikael Møller Høgsgaard, Kasper Green Larsen
2024	A*	`conf`	Replicable Learning of Large-Margin Halfspaces. ICML Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, Felix Zhou
2024	J	`jnl`	Replicable Learning of Large-Margin Halfspaces. CoRR Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, Felix Zhou
2024	A*	`conf`	Revisiting Agnostic PAC Learning. FOCS Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy
2024	J	`jnl`	Revisiting Agnostic PAC Learning. CoRR Steve Hanneke, Kasper Green Larsen, Nikita Zhivotovskiy
2024	A*	`conf`	Sparse Dimensionality Reduction Revisited. ICML Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, Chris Schwiegelshohn
2024	B	`conf`	Sublinear Time Shortest Path in Expander Graphs. MFCS Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen
2024	B	`conf`	The Impossibility of Parallelizing Boosting. ALT Amin Karbasi, Kasper Green Larsen
2024	A*	`conf`	The Many Faces of Optimal Weak-to-Strong Learning. NeurIPS Mikael Møller Høgsgaard, Kasper Green Larsen, Markus Engelund Mathiasen
2024	J	`jnl`	The Many Faces of Optimal Weak-to-Strong Learning. CoRR Mikael Møller Høgsgaard, Kasper Green Larsen, Markus Engelund Mathiasen
2024	A	`conf`	The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. ITCS Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
2024	J	`jnl`	The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. TheoretiCS Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
2023	A*	`conf`	AdaBoost is not an Optimal Weak to Strong Learner. ICML Mikael Møller Høgsgaard, Kasper Green Larsen, Martin Ritzert
2023	J	`jnl`	AdaBoost is not an Optimal Weak to Strong Learner. CoRR Mikael Møller Høgsgaard, Kasper Green Larsen, Martin Ritzert
2023	A*	`conf`	Bagging is an Optimal PAC Learner. COLT Kasper Green Larsen
2023	A	`conf`	Barriers for Faster Dimensionality Reduction. STACS Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
2023	J	`jnl`	Compressing Encrypted Data Over Small Fields. IACR Cryptol. ePrint Arch. Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
2023	J	`jnl`	Diagonalization Games. CoRR Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran
2023	J	`jnl`	Diagonalization Games. Electron. Colloquium Comput. Complex. Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran
2023	A	`conf`	Distributed Shuffling in Adversarial Environments. ITC Kasper Green Larsen, Maciej Obremski, Mark Simkin
2023	A*	`conf`	Fast Discrepancy Minimization with Hereditary Guarantees. SODA Kasper Green Larsen
2023	—	`conf`	How to Compress Encrypted Data. EUROCRYPT (1) Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
2023	J	`jnl`	Invertible Bloom Lookup Tables with Less Memory and Randomness. CoRR Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin
2023	J	`jnl`	Invertible Bloom Lookup Tables with Less Memory and Randomness. IACR Cryptol. ePrint Arch. Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin
2023	J	`jnl`	Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. CoRR Kasper Green Larsen, Rasmus Pagh, Toniann Pitassi, Or Zamir
2023	J	`jnl`	Sparse Dimensionality Reduction Revisited. CoRR Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, Chris Schwiegelshohn
2023	A*	`conf`	Stronger 3SUM-Indexing Lower Bounds. SODA Eldon Chung, Kasper Green Larsen
2023	J	`jnl`	Sublinear Time Shortest Path in Expander Graphs. CoRR Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen
2023	A*	`conf`	Super-Logarithmic Lower Bounds for Dynamic Graph Problems. FOCS Kasper Green Larsen, Huacheng Yu
2023	J	`jnl`	Super-Logarithmic Lower Bounds for Dynamic Graph Problems. CoRR Kasper Green Larsen, Huacheng Yu
2023	A*	`conf`	The Fast Johnson-Lindenstrauss Transform Is Even Faster. ICML Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
2023	J	`jnl`	The Impossibility of Parallelizing Boosting. CoRR Amin Karbasi, Kasper Green Larsen
2023	J	`jnl`	The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. CoRR Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
2022	J	`jnl`	Bagging is an Optimal PAC Learner. CoRR Kasper Green Larsen
2022	J	`jnl`	Barriers for Faster Dimensionality Reduction. CoRR Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
2022	J	`jnl`	Distributed Shuffling in Adversarial Environments. IACR Cryptol. ePrint Arch. Kasper Green Larsen, Maciej Obremski, Mark Simkin
2022	J	`jnl`	Fast Discrepancy Minimization with Hereditary Guarantees. CoRR Kasper Green Larsen
2022	B	`conf`	Hierarchical Categories in Colored Searching. ISAAC Peyman Afshani, Rasmus Killmann, Kasper Green Larsen
2022	J	`jnl`	Hierarchical Categories in Colored Searching. CoRR Peyman Afshani, Rasmus Killmann, Kasper Green Larsen
2022	J	`jnl`	How to Compress Encrypted Data. IACR Cryptol. ePrint Arch. Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
2022	A*	`conf`	Improved Coresets for Euclidean k-Means. NeurIPS Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar
2022	J	`jnl`	Improved Coresets for Euclidean k-Means. CoRR Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, Omar Ali Sheikh-Omar
2022	A*	`conf`	Optimal Weak to Strong Learning. NeurIPS Kasper Green Larsen, Martin Ritzert
2022	J	`jnl`	Optimal Weak to Strong Learning. CoRR Kasper Green Larsen, Martin Ritzert
2022	A*	`conf`	Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. SoCG Yair Bartal, Ora Nova Fandina, Kasper Green Larsen
2022	—	`conf`	Property-Preserving Hash Functions for Hamming Distance from Standard Assumptions. EUROCRYPT (2) Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
2022	J	`jnl`	Stronger 3SUM-Indexing Lower Bounds. CoRR Eldon Chung, Kasper Green Larsen
2022	J	`jnl`	The Fast Johnson-Lindenstrauss Transform is Even Faster. CoRR Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen
2022	J	`jnl`	Towards Optimal Lower Bounds for k-median and k-means Coresets. CoRR Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn
2022	A*	`conf`	Towards optimal lower bounds for k-median and k-means coresets. STOC Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn
2021	A	`conf`	Broadcast Secret-Sharing, Bounds and Applications. ITC Ivan Bjerre Damgård, Kasper Green Larsen, Sophia Yakoubov
2021	A*	`conf`	CountSketches, Feature Hashing and the Median of Three. ICML Kasper Green Larsen, Rasmus Pagh, Jakub Tetek
2021	J	`jnl`	CountSketches, Feature Hashing and the Median of Three. CoRR Kasper Green Larsen, Rasmus Pagh, Jakub Tetek
2021	—	`conf`	Further Unifying the Landscape of Cell Probe Lower Bounds. SOSA Kasper Green Larsen, Jonathan Lindegaard Starup, Jesper Steensgaard
2021	A*	`conf`	Optimal Oblivious Priority Queues. SODA Zahra Jafargholi, Kasper Green Larsen, Mark Simkin
2021	J	`jnl`	Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. CoRR Yair Bartal, Ora Nova Fandina, Kasper Green Larsen
2021	J	`jnl`	Property-Preserving Hash Functions from Standard Assumptions. CoRR Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
2021	J	`jnl`	Property-Preserving Hash Functions from Standard Assumptions. IACR Cryptol. ePrint Arch. Nils Fleischhacker, Kasper Green Larsen, Mark Simkin
2020	A*	`conf`	Clustering with a faulty oracle. WWW Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis
2020	J	`jnl`	Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. SIAM J. Comput. Kasper Green Larsen, Omri Weinstein, Huacheng Yu
2020	J	`jnl`	Further Unifying the Landscape of Cell Probe Lower Bounds. CoRR Kasper Green Larsen, Jonathan Lindegaard Starup, Jesper Steensgaard
2020	—	`conf`	Lower Bounds for Multi-server Oblivious RAMs. TCC (1) Kasper Green Larsen, Mark Simkin, Kevin Yeo
2020	A*	`conf`	Lower Bounds for Oblivious Near-Neighbor Search. SODA Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
2020	J	`jnl`	Lower bounds for external memory integer sorting via network coding. Commun. ACM Alireza Farhadi, Mohammad Taghi Hajiaghayi, Kasper Green Larsen, Elaine Shi
2020	A*	`conf`	Margins are Insufficient for Explaining Gradient Boosting. NeurIPS Allan Grønlund, Lior Kamma, Kasper Green Larsen
2020	J	`jnl`	Margins are Insufficient for Explaining Gradient Boosting. CoRR Allan Grønlund, Lior Kamma, Kasper Green Larsen
2020	A*	`conf`	Near-Tight Margin-Based Generalization Bounds for Support Vector Machines. ICML Allan Grønlund, Lior Kamma, Kasper Green Larsen
2020	J	`jnl`	Near-Tight Margin-Based Generalization Bounds for Support Vector Machines. CoRR Allan Grønlund, Lior Kamma, Kasper Green Larsen
2020	J	`jnl`	On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms. Algorithmica Casper Benjamin Freksen, Kasper Green Larsen
2020	B	`conf`	Optimal Learning of Joint Alignments with a Faulty Oracle. ISIT Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis
2020	Misc	`conf`	Optimal Learning of Joint Alignments with a Faulty Oracle. ITA Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis
2020	Misc	`conf`	Secret Sharing Lower Bound: Either Reconstruction is Hard or Shares are Long. SCN Kasper Green Larsen, Mark Simkin
2019	A*	`conf`	A Faster External Memory Priority Queue with DecreaseKeys. SODA Shunhua Jiang, Kasper Green Larsen
2019	—	`conf`	Communication Lower Bounds for Statistically Secure MPC, With or Without Preprocessing. CRYPTO (2) Ivan Damgård, Kasper Green Larsen, Jesper Buus Nielsen
2019	J	`jnl`	Communication Lower Bounds for Statistically Secure MPC, with or without Preprocessing. IACR Cryptol. ePrint Arch. Ivan Damgård, Kasper Green Larsen, Jesper Buus Nielsen
2019	A	`conf`	Constructive Discrepancy Minimization with Hereditary L2 Guarantees. STACS Kasper Green Larsen
2019	—	`ch.`	Dimension Reduction. Encyclopedia of Big Data Technologies Kasper Green Larsen
2019	J	`jnl`	Exponential Lower Bounds for Secret Sharing. IACR Cryptol. ePrint Arch. Kasper Green Larsen, Mark Simkin
2019	J	`jnl`	Heavy hitters via cluster-preserving clustering. Commun. ACM Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup
2019	J	`jnl`	Lower Bounds for External Memory Integer Sorting via Network Coding. SIAM J. Comput. Alireza Farhadi, Mohammad Taghi Hajiaghayi, Kasper Green Larsen, Elaine Shi
2019	J	`jnl`	Lower Bounds for Multi-Server Oblivious RAMs. IACR Cryptol. ePrint Arch. Kasper Green Larsen, Mark Simkin, Kevin Yeo
2019	A*	`conf`	Lower Bounds for Multiplication via Network Coding. ICALP Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen
2019	J	`jnl`	Lower Bounds for Multiplication via Network Coding. CoRR Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen
2019	A*	`conf`	Lower Bounds for Oblivious Data Structures. SODA Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen
2019	J	`jnl`	Lower Bounds for Oblivious Near-Neighbor Search. CoRR Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
2019	J	`jnl`	Lower Bounds for Oblivious Near-Neighbor Search. Electron. Colloquium Comput. Complex. Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
2019	J	`jnl`	Lower Bounds for Oblivious Near-Neighbor Search. IACR Cryptol. ePrint Arch. Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
2019	A*	`conf`	Lower bounds for external memory integer sorting via network coding. STOC Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, Elaine Shi
2019	A*	`conf`	Margin-Based Generalization Lower Bounds for Boosted Classifiers. NeurIPS Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson
2019	J	`jnl`	Margin-Based Generalization Lower Bounds for Boosted Classifiers. CoRR Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson
2019	J	`jnl`	Optimal Learning of Joint Alignments with a Faulty Oracle. CoRR Kasper Green Larsen, Michael Mitzenmacher, Charalampos E. Tsourakakis
2019	A*	`conf`	Optimal Minimal Margin Maximization with Boosting. ICML Alexander Mathiasen, Kasper Green Larsen, Allan Grønlund
2019	J	`jnl`	Optimal Minimal Margin Maximization with Boosting. CoRR Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen
2019	J	`jnl`	Optimal Oblivious Priority Queues and Offline Oblivious RAM. IACR Cryptol. ePrint Arch. Zahra Jafargholi, Kasper Green Larsen, Mark Simkin
2019	J	`jnl`	The query complexity of a permutation-based variant of Mastermind. Discret. Appl. Math. Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, Kurt Mehlhorn
2018	J	`jnl`	A Faster External Memory Priority Queue with DecreaseKeys. CoRR Shunhua Jiang, Kasper Green Larsen
2018	Misc	`conf`	Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. ITA Kasper Green Larsen, Omri Weinstein, Huacheng Yu
2018	A*	`conf`	Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds. STOC Kasper Green Larsen, Omri Weinstein, Huacheng Yu
2018	A*	`conf`	Fully Understanding The Hashing Trick. NeurIPS Lior Kamma, Casper Benjamin Freksen, Kasper Green Larsen
2018	J	`jnl`	Fully Understanding the Hashing Trick. CoRR Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen
2018	J	`jnl`	Lower Bounds for External Memory Integer Sorting via Network Coding. CoRR Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, Elaine Shi
2018	J	`jnl`	Lower Bounds for Oblivious Data Structures. CoRR Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen
2018	J	`jnl`	The Query Complexity of a Permutation-Based Variant of Mastermind. CoRR Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, Kurt Mehlhorn
2018	A*	`conf`	Tight cell probe bounds for succinct Boolean matrix-vector multiplication. STOC Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen
2018	A	`conf`	Upper and Lower Bounds for Dynamic Data Structures on Strings. STACS Raphaël Clifford, Allan Grønlund, Kasper Green Larsen, Tatiana Starikovskaya
2018	J	`jnl`	Upper and lower bounds for dynamic data structures on strings. CoRR Raphaël Clifford, Allan Grønlund, Kasper Green Larsen, Tatiana Starikovskaya
2018	—	`conf`	Yes, There is an Oblivious RAM Lower Bound! CRYPTO (2) Kasper Green Larsen, Jesper Buus Nielsen
2018	J	`jnl`	Yes, There is an Oblivious RAM Lower Bound! Electron. Colloquium Comput. Complex. Kasper Green Larsen, Jesper Buus Nielsen
2018	J	`jnl`	Yes, There is an Oblivious RAM Lower Bound! IACR Cryptol. ePrint Arch. Kasper Green Larsen, Jesper Buus Nielsen
2017	A*	`conf`	A Dichotomy for Regular Expression Membership Testing. FOCS Karl Bringmann, Allan Grønlund, Kasper Green Larsen
2017	J	`jnl`	Constructive Discrepancy Minimization with Hereditary L2 Guarantees. CoRR Kasper Green Larsen
2017	J	`jnl`	Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. CoRR Kasper Green Larsen, Omri Weinstein, Huacheng Yu
2017	J	`jnl`	Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. Electron. Colloquium Comput. Complex. Kasper Green Larsen, Omri Weinstein, Huacheng Yu
2017	A*	`conf`	DecreaseKeys are expensive for external memory priority queues. STOC Kasper Eenberg, Kasper Green Larsen, Huacheng Yu
2017	J	`jnl`	Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D. CoRR Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen
2017	A*	`conf`	Faster Online Matrix-Vector Multiplication. SODA Kasper Green Larsen, R. Ryan Williams
2017	B	`conf`	On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms. ISAAC Casper Benjamin Freksen, Kasper Green Larsen
2017	J	`jnl`	On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms. CoRR Casper Benjamin Freksen, Kasper Green Larsen
2017	A*	`conf`	Optimality of the Johnson-Lindenstrauss Lemma. FOCS Kasper Green Larsen, Jelani Nelson
2017	J	`jnl`	Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication. CoRR Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen
2016	J	`jnl`	A Dichotomy for Regular Expression Membership Testing. CoRR Karl Bringmann, Allan Grønlund, Kasper Green Larsen
2016	J	`jnl`	DecreaseKeys are Expensive for External Memory Priority Queues. CoRR Kasper Eenberg, Kasper Green Larsen, Huacheng Yu
2016	J	`jnl`	Faster Online Matrix-Vector Multiplication. CoRR Kasper Green Larsen, Ryan Williams
2016	A*	`conf`	Heavy Hitters via Cluster-Preserving Clustering. FOCS Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup
2016	J	`jnl`	Heavy hitters via cluster-preserving clustering. CoRR Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup
2016	—	`conf`	How to Prove Knowledge of Small Secrets. CRYPTO (3) Carsten Baum, Ivan Damgård, Kasper Green Larsen, Michael Nielsen
2016	J	`jnl`	How to prove knowledge of small secrets. IACR Cryptol. ePrint Arch. Carsten Baum, Ivan Damgård, Kasper Green Larsen, Michael Nielsen
2016	J	`jnl`	Optimality of the Johnson-Lindenstrauss Lemma. CoRR Kasper Green Larsen, Jelani Nelson
2016	A*	`conf`	The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. ICALP Kasper Green Larsen, Jelani Nelson
2016	A*	`conf`	Towards Tight Lower Bounds for Range Reporting on the RAM. ICALP Allan Grønlund, Kasper Green Larsen
2015	J	`jnl`	Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures. Theory Comput. Joshua Brody, Kasper Green Larsen
2015	A*	`conf`	Approximate Range Emptiness in Constant Time and Optimal Space. SODA Mayank Goswami, Allan Grønlund Jørgensen, Kasper Green Larsen, Rasmus Pagh
2015	A*	`conf`	New Unconditional Hardness Results for Dynamic and Online Problems. FOCS Raphaël Clifford, Allan Grønlund, Kasper Green Larsen
2015	J	`jnl`	New Unconditional Hardness Results for Dynamic and Online Problems. CoRR Raphaël Clifford, Allan Grønlund Jørgensen, Kasper Green Larsen
2015	J	`jnl`	On hardness of several string indexing problems. Theor. Comput. Sci. Kasper Green Larsen, J. Ian Munro, Jesper Sindahl Nielsen, Sharma V. Thankachan
2015	A*	`conf`	Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms. STOC Kasper Green Larsen, Jelani Nelson, Huy L. Nguyên
2014	J	`jnl`	Approximate Range Emptiness in Constant Time and Optimal Space. CoRR Mayank Goswami, Allan Grønlund Jørgensen, Kasper Green Larsen, Rasmus Pagh
2014	J	`jnl`	Linear-Space Data Structures for Range Mode Query in Arrays. Theory Comput. Syst. Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, Bryan T. Wilkinson
2014	A*	`conf`	Near-optimal labeling schemes for nearest common ancestors. SODA Stephen Alstrup, Esben Bistrup Halvorsen, Kasper Green Larsen
2014	B	`conf`	On Hardness of Several String Indexing Problems. CPM Kasper Green Larsen, J. Ian Munro, Jesper Sindahl Nielsen, Sharma V. Thankachan
2014	J	`jnl`	On Range Searching in the Group Model and Combinatorial Discrepancy. SIAM J. Comput. Kasper Green Larsen
2014	—	`conf`	Optimal Planar Orthogonal Skyline Counting Queries. SWAT Gerth Stølting Brodal, Kasper Green Larsen
2014	J	`jnl`	The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction. CoRR Kasper Green Larsen, Jelani Nelson
2014	J	`jnl`	Time lower bounds for nonadaptive turnstile streaming algorithms. CoRR Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen
2014	J	`jnl`	Towards Tight Lower Bounds for Range Reporting on the RAM. CoRR Allan Grønlund Jørgensen, Kasper Green Larsen
2013	J	`jnl`	(Approximate) Uncertain Skylines. Theory Comput. Syst. Peyman Afshani, Pankaj K. Agarwal, Lars Arge, Kasper Green Larsen, Jeff M. Phillips
2013	A*	`conf`	Near-Optimal Range Reporting Structures for Categorical Data. SODA Kasper Green Larsen, Freek van Walderveen
2013	J	`jnl`	Near-optimal labeling schemes for nearest common ancestors. CoRR Stephen Alstrup, Esben Bistrup Halvorsen, Kasper Green Larsen
2013	J	`jnl`	Optimal Planar Orthogonal Skyline Counting Queries CoRR Gerth Stølting Brodal, Kasper Green Larsen
2013	A*	`conf`	Succinct sampling from discrete distributions. STOC Karl Bringmann, Kasper Green Larsen
2013	—	`conf`	The Query Complexity of Finding a Hidden Permutation. Space-Efficient Data Structures, Streams, and Algorithms Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, Kurt Mehlhorn
2012	J	`jnl`	Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures CoRR Joshua Brody, Kasper Green Larsen
2012	A*	`conf`	Higher Cell Probe Lower Bounds for Evaluating Polynomials. FOCS Kasper Green Larsen
2012	—	`conf`	Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model. SCG Peyman Afshani, Lars Arge, Kasper Green Larsen
2012	A*	`conf`	I/O-efficient data structures for colored range and prefix reporting. SODA Kasper Green Larsen, Rasmus Pagh
2012	J	`jnl`	I/O-efficient spatial data structures for range queries. ACM SIGSPATIAL Special Lars Arge, Kasper Green Larsen
2012	—	`conf`	Improved range searching lower bounds. SCG Kasper Green Larsen, Huy Le Nguyen
2012	A	`conf`	Linear-Space Data Structures for Range Mode Query in Arrays. STACS Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, Bryan T. Wilkinson
2012	J	`jnl`	The Deterministic and Randomized Query Complexity of a Simple Guessing Game. Electron. Colloquium Comput. Complex. Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Winzen, Kasper Green Larsen, Kurt Mehlhorn
2012	A*	`conf`	The cell probe complexity of dynamic range counting. STOC Kasper Green Larsen
2011	A	`conf`	(Approximate) uncertain skylines. ICDT Peyman Afshani, Pankaj K. Agarwal, Lars Arge, Kasper Green Larsen, Jeff M. Phillips
2011	J	`jnl`	I/O-Efficient Data Structures for Colored Range and Prefix Reporting CoRR Kasper Green Larsen, Rasmus Pagh
2011	A*	`conf`	On Range Searching in the Group Model and Combinatorial Discrepancy. FOCS Kasper Green Larsen
2011	J	`jnl`	Orthogonal Range Searching on the RAM, Revisited CoRR Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu
2011	—	`conf`	Orthogonal range searching on the RAM, revisited. SCG Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu
2011	A*	`conf`	Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures. SODA Allan Grønlund Jørgensen, Kasper Green Larsen
2011	J	`jnl`	The Cell Probe Complexity of Dynamic Range Counting CoRR Kasper Green Larsen
2010	—	`conf`	Cleaning massive sonar point clouds. GIS Lars Arge, Kasper Green Larsen, Thomas Mølhave, Freek van Walderveen