Kasper Green Larsen
According to our database^{1},
Kasper Green Larsen
authored at least 44 papers
between 2007 and 2019.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at cs.au.dk
On csauthors.net:
Bibliography
2019
A Faster External Memory Priority Queue with DecreaseKeys.
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
Lower Bounds for Oblivious Data Structures.
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
2018
Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018
Tight cell probe bounds for succinct Boolean matrixvector multiplication.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018
Upper and Lower Bounds for Dynamic Data Structures on Strings.
Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018
Fully Understanding The Hashing Trick.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.
Proceedings of the 2018 Information Theory and Applications Workshop, 2018
Yes, There is an Oblivious RAM Lower Bound!
Proceedings of the Advances in Cryptology  CRYPTO 2018, 2018
2017
DecreaseKeys are expensive for external memory priority queues.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
Faster Online MatrixVector Multiplication.
Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, 2017
On Using Toeplitz and Circulant Matrices for JohnsonLindenstrauss Transforms.
Proceedings of the 28th International Symposium on Algorithms and Computation, 2017
Optimality of the JohnsonLindenstrauss Lemma.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017
A Dichotomy for Regular Expression Membership Testing.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017
2016
The JohnsonLindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016
Towards Tight Lower Bounds for Range Reporting on the RAM.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016
Heavy Hitters via ClusterPreserving Clustering.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016
How to Prove Knowledge of Small Secrets.
Proceedings of the Advances in Cryptology  CRYPTO 2016, 2016
2015
Adapt or Die: Polynomial Lower Bounds for NonAdaptive Dynamic Data Structures.
Theory of Computing, 2015
Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms.
Proceedings of the FortySeventh Annual ACM on Symposium on Theory of Computing, 2015
Approximate Range Emptiness in Constant Time and Optimal Space.
Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, 2015
New Unconditional Hardness Results for Dynamic and Online Problems.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015
2014
Optimal Planar Orthogonal Skyline Counting Queries.
Proceedings of the Algorithm Theory  SWAT 2014, 2014
Nearoptimal labeling schemes for nearest common ancestors.
Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms, 2014
On Hardness of Several String Indexing Problems.
Proceedings of the Combinatorial Pattern Matching  25th Annual Symposium, 2014
2013
Succinct sampling from discrete distributions.
Proceedings of the Symposium on Theory of Computing Conference, 2013
NearOptimal Range Reporting Structures for Categorical Data.
Proceedings of the TwentyFourth Annual ACMSIAM Symposium on Discrete Algorithms, 2013
The Query Complexity of Finding a Hidden Permutation.
Proceedings of the SpaceEfficient Data Structures, 2013
2012
I/Oefficient spatial data structures for range queries.
SIGSPATIAL Special, 2012
The Deterministic and Randomized Query Complexity of a Simple Guessing Game.
Electronic Colloquium on Computational Complexity (ECCC), 2012
The cell probe complexity of dynamic range counting.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
LinearSpace Data Structures for Range Mode Query in Arrays.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012
I/Oefficient data structures for colored range and prefix reporting.
Proceedings of the TwentyThird Annual ACMSIAM Symposium on Discrete Algorithms, 2012
Higher Cell Probe Lower Bounds for Evaluating Polynomials.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012
Improved range searching lower bounds.
Proceedings of the Symposuim on Computational Geometry 2012, 2012
Higherdimensional orthogonal range reporting and rectangle stabbing in the pointer machine model.
Proceedings of the Symposuim on Computational Geometry 2012, 2012
2011
Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures.
Proceedings of the TwentySecond Annual ACMSIAM Symposium on Discrete Algorithms, 2011
(Approximate) uncertain skylines.
Proceedings of the Database Theory, 2011
On Range Searching in the Group Model and Combinatorial Discrepancy.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
Orthogonal range searching on the RAM, revisited.
Proceedings of the 27th ACM Symposium on Computational Geometry, 2011
2010
Cell Probe Lower Bounds and Approximations for Range Mode.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010
Cleaning massive sonar point clouds.
Proceedings of the 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, 2010
Orthogonal range reporting: query lower bounds, optimal structures in 3d, and higherdimensional improvements.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010
2009
Orthogonal Range Reporting in Three and Higher Dimensions.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009
2007
Mental models and programming aptitude.
Proceedings of the 12th Annual SIGCSE Conference on Innovation and Technology in Computer Science Education, 2007