Kasper Green Larsen

According to our database1, Kasper Green Larsen authored at least 72 papers between 2007 and 2018.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Yes, There is an Oblivious RAM Lower Bound!
IACR Cryptology ePrint Archive, 2018

Yes, There is an Oblivious RAM Lower Bound!
Electronic Colloquium on Computational Complexity (ECCC), 2018

A Faster External Memory Priority Queue with DecreaseKeys.
CoRR, 2018

Fully Understanding the Hashing Trick.
CoRR, 2018

Upper and lower bounds for dynamic data structures on strings.
CoRR, 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 matrix-vector 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

Yes, There is an Oblivious RAM Lower Bound!
Proceedings of the Advances in Cryptology - CRYPTO 2018, 2018

2017
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication.
CoRR, 2017

Constructive Discrepancy Minimization with Hereditary L2 Guarantees.
CoRR, 2017

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.
CoRR, 2017

Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D.
CoRR, 2017

On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms.
CoRR, 2017

DecreaseKeys are expensive for external memory priority queues.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Faster Online Matrix-Vector Multiplication.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms.
Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

Optimality of the Johnson-Lindenstrauss 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
How to prove knowledge of small secrets.
IACR Cryptology ePrint Archive, 2016

Faster Online Matrix-Vector Multiplication.
CoRR, 2016

Heavy hitters via cluster-preserving clustering.
CoRR, 2016

Optimality of the Johnson-Lindenstrauss Lemma.
CoRR, 2016

DecreaseKeys are Expensive for External Memory Priority Queues.
CoRR, 2016

A Dichotomy for Regular Expression Membership Testing.
CoRR, 2016

The Johnson-Lindenstrauss 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 Cluster-Preserving 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 Non-Adaptive Dynamic Data Structures.
Theory of Computing, 2015

On hardness of several string indexing problems.
Theor. Comput. Sci., 2015

New Unconditional Hardness Results for Dynamic and Online Problems.
CoRR, 2015

Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximate Range Emptiness in Constant Time and Optimal Space.
Proceedings of the Twenty-Sixth Annual ACM-SIAM 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
On Range Searching in the Group Model and Combinatorial Discrepancy.
SIAM J. Comput., 2014

Linear-Space Data Structures for Range Mode Query in Arrays.
Theory Comput. Syst., 2014

Time lower bounds for nonadaptive turnstile streaming algorithms.
CoRR, 2014

The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction.
CoRR, 2014

Towards Tight Lower Bounds for Range Reporting on the RAM.
CoRR, 2014

Approximate Range Emptiness in Constant Time and Optimal Space.
CoRR, 2014

Optimal Planar Orthogonal Skyline Counting Queries.
Proceedings of the Algorithm Theory - SWAT 2014, 2014

Near-optimal labeling schemes for nearest common ancestors.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

On Hardness of Several String Indexing Problems.
Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

2013
(Approximate) Uncertain Skylines.
Theory Comput. Syst., 2013

Optimal Planar Orthogonal Skyline Counting Queries
CoRR, 2013

Near-optimal labeling schemes for nearest common ancestors.
CoRR, 2013

Succinct sampling from discrete distributions.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Near-Optimal Range Reporting Structures for Categorical Data.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

The Query Complexity of Finding a Hidden Permutation.
Proceedings of the Space-Efficient Data Structures, 2013

2012
I/O-efficient 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

Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
CoRR, 2012

The cell probe complexity of dynamic range counting.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Linear-Space Data Structures for Range Mode Query in Arrays.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

I/O-efficient data structures for colored range and prefix reporting.
Proceedings of the Twenty-Third Annual ACM-SIAM 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

Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model.
Proceedings of the Symposuim on Computational Geometry 2012, 2012

2011
The Cell Probe Complexity of Dynamic Range Counting
CoRR, 2011

I/O-Efficient Data Structures for Colored Range and Prefix Reporting
CoRR, 2011

Orthogonal Range Searching on the RAM, Revisited
CoRR, 2011

Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures.
Proceedings of the Twenty-Second Annual ACM-SIAM 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 3-d, and higher-dimensional 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


  Loading...