Kasper Green Larsen

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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
Near-Tight Margin-Based Generalization Bounds for Support Vector Machines.
CoRR, 2020

On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms.
Algorithmica, 2020

Clustering with a faulty oracle.
Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020

2019
Dimension Reduction.
Proceedings of the Encyclopedia of Big Data Technologies., 2019

Lower Bounds for Multi-Server Oblivious RAMs.
IACR Cryptol. ePrint Arch., 2019

Exponential Lower Bounds for Secret Sharing.
IACR Cryptol. ePrint Arch., 2019

Optimal Oblivious Priority Queues and Offline Oblivious RAM.
IACR Cryptol. ePrint Arch., 2019

Communication Lower Bounds for Statistically Secure MPC, with or without Preprocessing.
IACR Cryptol. ePrint Arch., 2019

Lower Bounds for Oblivious Near-Neighbor Search.
Electronic Colloquium on Computational Complexity (ECCC), 2019

The query complexity of a permutation-based variant of Mastermind.
Discret. Appl. Math., 2019

Optimal Learning of Joint Alignments with a Faulty Oracle.
CoRR, 2019

Heavy hitters via cluster-preserving clustering.
Commun. ACM, 2019

Lower bounds for external memory integer sorting via network coding.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Constructive Discrepancy Minimization with Hereditary L2 Guarantees.
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

A Faster External Memory Priority Queue with DecreaseKeys.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Lower Bounds for Oblivious Data Structures.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Margin-Based Generalization Lower Bounds for Boosted Classifiers.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Optimal Minimal Margin Maximization with Boosting.
Proceedings of the 36th International Conference on Machine Learning, 2019

Lower Bounds for Multiplication via Network Coding.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
Yes, There is an Oblivious RAM Lower Bound!
Electronic Colloquium on Computational Complexity (ECCC), 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

Fully Understanding The Hashing Trick.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

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

Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D.
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

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 Cryptol. ePrint Arch., 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

2015
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures.
Theory Comput., 2015

On hardness of several string indexing problems.
Theor. Comput. Sci., 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

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

2013
(Approximate) Uncertain Skylines.
Theory Comput. Syst., 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.
ACM 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

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
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

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...