Dominik Kempa

Affiliations:
  • Stony Brook University, Stony Brook, NY, USA
  • Johns Hopkins University, Department of Computer Science, Baltimore, MD, USA (former)
  • University of California, Berkeley, CA, USA (former)
  • University of Warwick, Department of Computer Science, UK (former)
  • University of Helsinki, Department of Computer Science, Finland (former, PhD 2015)


According to our database1, Dominik Kempa authored at least 45 papers between 2012 and 2023.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data.
CoRR, 2023

Breaking the 𝒪(<i>n</i>)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022
Resolution of the burrows-wheeler transform conjecture.
Commun. ACM, 2022

Dynamic suffix array with polylogarithmic queries and updates.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

An Upper Bound and Linear-Space Queries on the LZ-End Parsing.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021
Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays.
CoRR, 2021

Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing.
Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2019
Better External Memory LCP Array Construction.
ACM J. Exp. Algorithmics, 2019

Fixed Block Compression Boosting in FM-Indexes: Theory and Practice.
Algorithmica, 2019

String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Optimal Construction of Compressed Indexes for Highly Repetitive Texts.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018
Diverse Palindromic Factorization is NP-Complete.
Int. J. Found. Comput. Sci., 2018

At the roots of dictionary compression: string attractors.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

String Attractors: Verification and Optimization.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Hybrid Indexing Revisited.
Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments, 2018

2017
Engineering a Lightweight External Memory Suffix Array Construction Algorithm.
Math. Comput. Sci., 2017

Closing in on Time and Space Optimal Construction of Compressed Indexes.
CoRR, 2017

Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet.
Proceedings of the 16th International Symposium on Experimental Algorithms, 2017

On the Size of Lempel-Ziv and Lyndon Factorizations.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

LZ-End Parsing in Linear Time.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

LZ-End Parsing in Compressed Space.
Proceedings of the 2017 Data Compression Conference, 2017

Engineering External Memory Induced Suffix Sorting.
Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments, 2017

2016
Tighter bounds for the sum of irreducible LCP values.
Theor. Comput. Sci., 2016

Lazy Lempel-Ziv Factorization Algorithms.
ACM J. Exp. Algorithmics, 2016

LCP Array Construction in External Memory.
ACM J. Exp. Algorithmics, 2016

Lempel-Ziv Decoding in External Memory.
Proceedings of the Experimental Algorithms - 15th International Symposium, 2016

LCP Array Construction Using O(sort(n)) (or Less) I/Os.
Proceedings of the String Processing and Information Retrieval, 2016

Faster External Memory LCP Array Construction.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Faster, Minuter.
Proceedings of the 2016 Data Compression Conference, 2016

2015
Efficient Construction of Fundamental Data Structures in Large-Scale Text Indexing.
PhD thesis, 2015

Diverse Palindromic Factorization is NP-Complete.
CoRR, 2015

Diverse Palindromic Factorization Is NP-complete.
Proceedings of the Developments in Language Theory - 19th International Conference, 2015

Parallel External Memory Suffix Sorting.
Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

2014
A subquadratic algorithm for minimum palindromic factorization.
J. Discrete Algorithms, 2014

Faster Sparse Suffix Sorting.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Hybrid Compression of Bitvectors for the FM-Index.
Proceedings of the Data Compression Conference, 2014

Lempel-Ziv Parsing in External Memory.
Proceedings of the Data Compression Conference, 2014

String Range Matching.
Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

2013
Lightweight Lempel-Ziv Parsing.
Proceedings of the Experimental Algorithms, 12th International Symposium, 2013

Crochemore's String Matching Algorithm: Simplification, Extensions, Applications.
Proceedings of the Prague Stringology Conference 2013, Prague, Czech Republic, 2013

Linear Time Lempel-Ziv Factorization: Simple, Fast, Small.
Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

Lempel-Ziv factorization: Simple, fast, practical.
Proceedings of the 15th Meeting on Algorithm Engineering and Experiments, 2013

2012
Grammar Precompression Speeds Up Burrows-Wheeler Compression.
Proceedings of the String Processing and Information Retrieval, 2012

Slashing the Time for BWT Inversion.
Proceedings of the 2012 Data Compression Conference, Snowbird, UT, USA, April 10-12, 2012, 2012


  Loading...