Publications
Rajat De, Dominik Kempa: Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data, SODA 2024 DOI | Arxiv
Dominik Kempa, Tomasz Kociumaka: Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space, FOCS 2023 DOI | Arxiv
Dominik Kempa, Tomasz Kociumaka: Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees, SODA 2023 DOI | Arxiv
Dominik Kempa, Tomasz Kociumaka: Dynamic Suffix Array with Polylogarithmic Queries and Updates, STOC 2022 DOI | Arxiv
Dominik Kempa, Barna Saha: An Upper Bound and Linear-Space Queries on the LZ-End Parsing, SODA 2022 DOI | Slides | Video
Dominik Kempa, Ben Langmead: Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing, ESA 2021 DOI | Arxiv | Code | Slides | Video
Dominik Kempa, Tomasz Kociumaka: Resolution of the Burrows-Wheeler Transform Conjecture, FOCS 2020 DOI | Arxiv | Slides | Video
> Featured in CACM Research Highlights Intro | PaperDominik Kempa, Tomasz Kociumaka: String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure, STOC 2019 DOI | Poster | Arxiv
> Featured in CPM Highlights 2020
> Invited to AlgPie 2019
> Invited to Dagstuhl Seminar Slides
> Presented at HALG 2019 SlidesDominik Kempa: Optimal Construction of Compressed Indexes for Highly Repetitive Texts, SODA 2019 DOI | Arxiv
Simon Gog, Juha Kärkkäinen, Dominik Kempa, Matthias Petri, Simon J. Puglisi: Fixed Block Compression Boosting in FM-Indexes: Theory and Practice, Algorithmica 2019 DOI | Code
Juha Kärkkäinen, Dominik Kempa: Better External Memory LCP Array Construction, ACM J. Exp. 2019 DOI | Code
Dominik Kempa, Nicola Prezza: At the Roots of Dictionary Compression: String Attractors, STOC 2018 DOI | Poster | Arxiv
> Featured in CPM Highlights 2019
> Presented at HALG 2018 SlidesHideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Shiho Sugimoto: Diverse Palindromic Factorization is NP-Complete, Int. J. Found. Comput. Sci. 2018 DOI
Héctor Ferrada, Dominik Kempa, Simon J. Puglisi: Hybrid Indexing Revisited, ALENEX 2018 DOI
Dominik Kempa, Alberto Policriti, Nicola Prezza, Eva Rotenberg: String Attractors: Verification and Optimization, ESA 2018 DOI | Arxiv | Slides
Juha Kärkkäinen, Dominik Kempa: Engineering a Lightweight External Memory Suffix Array Construction Algorithm, Math. Comp. Sci. 2017 DOI | Code
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi, Bella Zhukova: Engineering External Memory Induced Suffix Sorting, ALENEX 2017 DOI | Code
Dominik Kempa, Dmitry Kosolobov: LZ-End Parsing in Compressed Space, DCC 2017 DOI | Code | Arxiv
Dominik Kempa, Dmitry Kosolobov: LZ-End Parsing in Linear Time, ESA 2017 DOI | Slides
Juha Kärkkäinen, Dominik Kempa, Yuto Nakashima, Simon J. Puglisi, Arseny M. Shur: On the Size of Lempel-Ziv and Lyndon Factorizations, STACS 2017 DOI | Slides
Juha Kärkkäinen, Dominik Kempa: Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet, SEA 2017 DOI | Code
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Lazy Lempel-Ziv Factorization Algorithms, ACM J. Exp. Algor. 2016 DOI | Code
Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski: Tighter Bounds for the Sum of Irreducible LCP Values, Theor. Comp. Sci. 2016 DOI
Simon Gog, Juha Kärkkäinen, Dominik Kempa, Matthias Petri, Simon J. Puglisi: Faster, Minuter, DCC 2016 DOI | Code
Juha Kärkkäinen, Dominik Kempa: Faster External Memory LCP Array Construction, ESA 2016 DOI | Code | Slides
> Invited to ACM JEA Special IssueJuha Kärkkäinen, Dominik Kempa: LCP Array Construction Using O(sort(n)) (or Less) I/Os, SPIRE 2016 DOI
Djamal Belazzougui, Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Lempel-Ziv Decoding in External Memory, SEA 2016 DOI | Arxiv | Code
Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski: Tighter Bounds for the Sum of Irreducible LCP Values, CPM 2015 DOI
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Parallel External Memory Suffix Sorting, CPM 2015 DOI | Code | Slides
Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Simon J. Puglisi, Shiho Sugimoto: Diverse Palindromic Factorization Is NP-complete, DLT 2015 DOI | Arxiv
Gabriele Fici, Travis Gagie, Juha Kärkkäinen, Dominik Kempa: A Subquadratic Algorithm for Minimum Palindromic Factorization, J. Discrete Algorithms 2014 DOI | Arxiv
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: String Range Matching, CPM 2014 DOI | Slides
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Lempel-Ziv Parsing in External Memory, DCC 2014 DOI | Arxiv | Code | Poster | Slides
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Hybrid Compression of Bitvectors for the FM-Index, DCC 2014 DOI | Code | Slides
Juha Kärkkäinen, Dominik Kempa: Engineering a Lightweight External Memory Suffix Array Construction Algorithm, ICABD 2014 DOI | Code
Tomohiro I, Juha Kärkkäinen, Dominik Kempa: Faster Sparse Suffix Sorting, STACS 2014 DOI
Juha Kärkkäinen, Dominik Kempa: LCP Array Construction in External Memory, SEA 2014 DOI | Code
> Invited to ACM JEA Special Issue
Dominik Kempa, Simon J. Puglisi: Lempel-Ziv Factorization: Simple, Fast, Practical, ALENEX 2013 DOI | Code
> Invited to ACM JEA Special IssueJuha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Linear Time Lempel-Ziv Factorization: Simple, Fast, Small, CPM 2013 DOI | Arxiv | Code | Slides
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Crochemore's String Matching Algorithm: Simplification, Extensions, Applications, PSC 2013 DOI
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Lightweight Lempel-Ziv Parsing, SEA 2013 DOI | Arxiv | Code