Kasper Green Larsen

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

Property-Preserving Hash Functions from Standard Assumptions.

[BibT_eX]

[DOI]

Nils Fleischhacker

IACR Cryptol. ePrint Arch., 2021

Further Unifying the Landscape of Cell Probe Lower Bounds.

[BibT_eX]

[DOI]

Jonathan Lindegaard Starup

Jesper Steensgaard

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Optimal Oblivious Priority Queues.

[BibT_eX]

[DOI]

Zahra Jafargholi

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

CountSketches, Feature Hashing and the Median of Three.

[BibT_eX]

[DOI]

Rasmus Pagh

Jakub Tetek

Proceedings of the 38th International Conference on Machine Learning, 2021

Broadcast Secret-Sharing, Bounds and Applications.

[BibT_eX]

[DOI]

Ivan Bjerre Damgård

Sophia Yakoubov

Proceedings of the 2nd Conference on Information-Theoretic Cryptography, 2021

2020

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

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

Omri Weinstein

Huacheng Yu

SIAM J. Comput., 2020

Lower bounds for external memory integer sorting via network coding.

[BibT_eX]

[DOI]

Alireza Farhadi

Elaine Shi

Commun. ACM, 2020

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

[BibT_eX]

[DOI]

Casper Benjamin Freksen

Algorithmica, 2020

Clustering with a faulty oracle.

[BibT_eX]

[DOI]

Charalampos E. Tsourakakis

Michael Mitzenmacher

Proceedings of the WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, 2020

Secret Sharing Lower Bound: Either Reconstruction is Hard or Shares are Long.

[BibT_eX]

[DOI]

Proceedings of the Security and Cryptography for Networks - 12th International Conference, 2020

Margins are Insufficient for Explaining Gradient Boosting.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Optimal Learning of Joint Alignments with a Faulty Oracle.

[BibT_eX]

[DOI]

Charalampos E. Tsourakakis

Michael Mitzenmacher

Proceedings of the IEEE International Symposium on Information Theory, 2020

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

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

2019

Dimension Reduction.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Big Data Technologies., 2019

Lower Bounds for Multi-Server Oblivious RAMs.

[BibT_eX]

[DOI]

Kevin Yeo

IACR Cryptol. ePrint Arch., 2019

Exponential Lower Bounds for Secret Sharing.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2019

Optimal Oblivious Priority Queues and Offline Oblivious RAM.

[BibT_eX]

[DOI]

Zahra Jafargholi

IACR Cryptol. ePrint Arch., 2019

Communication Lower Bounds for Statistically Secure MPC, with or without Preprocessing.

[BibT_eX]

[DOI]

Ivan Damgård

Jesper Buus Nielsen

IACR Cryptol. ePrint Arch., 2019

Lower Bounds for Oblivious Near-Neighbor Search.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

The query complexity of a permutation-based variant of Mastermind.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2019

Heavy hitters via cluster-preserving clustering.

[BibT_eX]

[DOI]

Commun. ACM, 2019

Constructive Discrepancy Minimization with Hereditary L2 Guarantees.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

A Faster External Memory Priority Queue with DecreaseKeys.

[BibT_eX]

[DOI]

Shunhua Jiang

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Lower Bounds for Oblivious Data Structures.

[BibT_eX]

[DOI]

Riko Jacob

Jesper Buus Nielsen

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Margin-Based Generalization Lower Bounds for Boosted Classifiers.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Alexander Mathiasen

Proceedings of the 36th International Conference on Machine Learning, 2019

Lower Bounds for Multiplication via Network Coding.

[BibT_eX]

[DOI]

Casper Benjamin Freksen

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Yes, There is an Oblivious RAM Lower Bound!

[BibT_eX]

[DOI]

Jesper Buus Nielsen

Electron. Colloquium Comput. Complex., 2018

Tight cell probe bounds for succinct Boolean matrix-vector multiplication.

[BibT_eX]

[DOI]

Diptarka Chakraborty

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Upper and Lower Bounds for Dynamic Data Structures on Strings.

[BibT_eX]

[DOI]

Raphaël Clifford

Tatiana Starikovskaya

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Fully Understanding The Hashing Trick.

[BibT_eX]

[DOI]

Casper Benjamin Freksen

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

2017

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

[BibT_eX]

[DOI]

Alexander Mathiasen

Jesper Sindahl Nielsen

CoRR, 2017

DecreaseKeys are expensive for external memory priority queues.

[BibT_eX]

[DOI]

Kasper Eenberg

Huacheng Yu

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Faster Online Matrix-Vector Multiplication.

[BibT_eX]

[DOI]

R. Ryan Williams

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Optimality of the Johnson-Lindenstrauss Lemma.

[BibT_eX]

[DOI]

Jelani Nelson

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

A Dichotomy for Regular Expression Membership Testing.

[BibT_eX]

[DOI]

Karl Bringmann

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

How to prove knowledge of small secrets.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2016

The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction.

[BibT_eX]

[DOI]

Jelani Nelson

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Towards Tight Lower Bounds for Range Reporting on the RAM.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Joshua Brody

Theory Comput., 2015

On hardness of several string indexing problems.

[BibT_eX]

[DOI]

J. Ian Munro

Jesper Sindahl Nielsen

Sharma V. Thankachan

Theor. Comput. Sci., 2015

Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms.

[BibT_eX]

[DOI]

Jelani Nelson

Huy L. Nguyên

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximate Range Emptiness in Constant Time and Optimal Space.

[BibT_eX]

[DOI]

Mayank Goswami

Allan Grønlund Jørgensen

Rasmus Pagh

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

New Unconditional Hardness Results for Dynamic and Online Problems.

[BibT_eX]

[DOI]

Raphaël Clifford

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

On Range Searching in the Group Model and Combinatorial Discrepancy.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Linear-Space Data Structures for Range Mode Query in Arrays.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Optimal Planar Orthogonal Skyline Counting Queries.

[BibT_eX]

[DOI]

Gerth Stølting Brodal

Proceedings of the Algorithm Theory - SWAT 2014, 2014

Near-optimal labeling schemes for nearest common ancestors.

[BibT_eX]

[DOI]

Stephen Alstrup

Esben Bistrup Halvorsen

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

(Approximate) Uncertain Skylines.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2013

Succinct sampling from discrete distributions.

[BibT_eX]

[DOI]

Karl Bringmann

Proceedings of the Symposium on Theory of Computing Conference, 2013

Near-Optimal Range Reporting Structures for Categorical Data.

[BibT_eX]

[DOI]

Freek van Walderveen

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

The Query Complexity of Finding a Hidden Permutation.

[BibT_eX]

[DOI]

Proceedings of the Space-Efficient Data Structures, 2013

2012

I/O-efficient spatial data structures for range queries.

[BibT_eX]

[DOI]

ACM SIGSPATIAL Special, 2012

The Deterministic and Randomized Query Complexity of a Simple Guessing Game.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

The cell probe complexity of dynamic range counting.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

I/O-efficient data structures for colored range and prefix reporting.

[BibT_eX]

[DOI]

Rasmus Pagh

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Higher Cell Probe Lower Bounds for Evaluating Polynomials.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Improved range searching lower bounds.

[BibT_eX]

[DOI]

Huy Le Nguyen

Proceedings of the 28th ACM Symposium on Computational Geometry, 2012

Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model.

[BibT_eX]

[DOI]

Proceedings of the 28th ACM Symposium on Computational Geometry, 2012

2011

Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures.

[BibT_eX]

[DOI]

Allan Grønlund Jørgensen

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Orthogonal range searching on the RAM, revisited.

[BibT_eX]

[DOI]

Timothy M. Chan

Mihai Patrascu

Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010

Cell Probe Lower Bounds and Approximations for Range Mode.

[BibT_eX]

[DOI]

Mark Greve

Allan Grønlund Jørgensen

Jakob Truelsen

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Cleaning massive sonar point clouds.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

2009

Orthogonal Range Reporting in Three and Higher Dimensions.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2007

Mental models and programming aptitude.

[BibT_eX]

[DOI]

Michael E. Caspersen