Publications

1. Dominik Kempa, Tomasz Kociumaka
   Tight Lower Bounds for Central String Queries in Compressed Space
   SODA 2026  Arxiv

2. Dominik Kempa, Tomasz Kociumaka
   Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
   SODA 2026  Arxiv

3. Rajat De, Dominik Kempa
   Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
   SODA 2026  Arxiv

4. Ankith Reddy Adudodla, Dominik Kempa
   Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text
   ALENEX 2026  Arxiv  |  Code

5. Dominik Kempa, Tomasz Kociumaka
   On the Hardness Hierarchy for the O(n √log n) Complexity in the Word RAM
   STOC 2025  DOI  |  Arxiv  |  Video (by Tomasz)
   > Invited to SICOMP Special Issue

6. Rajat De, Dominik Kempa
   Word Break on SLP-Compressed Texts
   DCC 2025  DOI  |  Arxiv

7. Dominik Kempa, Tomasz Kociumaka
   Lempel-Ziv (LZ77) Factorization in Sublinear Time
   FOCS 2024  DOI  |  Arxiv  |  Video

8. Rajat De, Dominik Kempa
   Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
   SODA 2024  DOI  |  Arxiv

9. Dominik Kempa, Tomasz Kociumaka
   Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
   FOCS 2023  DOI  |  Arxiv

10. Dominik Kempa, Tomasz Kociumaka
    Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees
    SODA 2023  DOI  |  Arxiv

11. Dominik Kempa, Tomasz Kociumaka
    Resolution of the Burrows-Wheeler Transform Conjecture
    Commun. of the ACM 2022  DOI

12. Dominik Kempa, Tomasz Kociumaka
    Dynamic Suffix Array with Polylogarithmic Queries and Updates
    STOC 2022  DOI  |  Arxiv

13. Dominik Kempa, Barna Saha
    An Upper Bound and Linear-Space Queries on the LZ-End Parsing
    SODA 2022   DOI  |  Slides  |  Video

14. Dominik Kempa, Ben Langmead
    Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing
    ESA 2021  DOI  |  Arxiv  |  Code  |  Slides  |  Video

15. Dominik Kempa, Tomasz Kociumaka
    Resolution of the Burrows-Wheeler Transform Conjecture
    FOCS 2020   DOI  |  Arxiv  |  Slides  |  Video
    > Featured in CACM Research Highlights   Intro  |  Paper 

16. Dominik 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   Slides

17. Dominik Kempa
    Optimal Construction of Compressed Indexes for Highly Repetitive Texts
    SODA 2019   DOI  |  Arxiv

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

19. Juha Kärkkäinen, Dominik Kempa
    Better External Memory LCP Array Construction
    ACM J. Exp.  2019  DOI  |  Code

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

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

22. Héctor Ferrada, Dominik Kempa, Simon J. Puglisi
    Hybrid Indexing Revisited
    ALENEX 2018   DOI

23. Dominik Kempa, Alberto Policriti, Nicola Prezza, Eva Rotenberg
    String Attractors: Verification and Optimization
    ESA 2018   DOI  |  Arxiv  |  Slides

24. Juha Kärkkäinen, Dominik Kempa
    Engineering a Lightweight External Memory Suffix Array Construction Algorithm
    Math. Comp. Sci. 2017
    DOI  |  Code

25. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi, Bella Zhukova
    Engineering External Memory Induced Suffix Sorting
    ALENEX 2017   DOI  |  Code

26. Dominik Kempa, Dmitry Kosolobov
    LZ-End Parsing in Compressed Space
    DCC 2017  DOI  |  Code  |  Arxiv

27. Dominik Kempa, Dmitry Kosolobov
    LZ-End Parsing in Linear Time
    ESA 2017  DOI  |  Slides

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

29. Juha Kärkkäinen, Dominik Kempa
    Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet
    SEA 2017   DOI  |  Code

30. Juha Kärkkäinen, Dominik Kempa
    LCP Array Construction in External Memory
    ACM J. Exp. Algor. 2016   DOI  |  Code

31. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
    Lazy Lempel-Ziv Factorization Algorithms
    ACM J. Exp. Algor. 2016   DOI  |  Code

32. Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski
    Tighter Bounds for the Sum of Irreducible LCP Values
    Theor. Comp. Sci. 2016   DOI

33. Simon Gog, Juha Kärkkäinen, Dominik Kempa, Matthias Petri, Simon J. Puglisi
    Faster, Minuter
    DCC 2016   DOI  |  Code

34. Juha Kärkkäinen, Dominik Kempa
    Faster External Memory LCP Array Construction
    ESA 2016   DOI  |  Code  |  Slides
    > Invited to ACM JEA Special Issue

35. Juha Kärkkäinen, Dominik Kempa
    LCP Array Construction Using O(sort(n)) (or Less) I/Os
    SPIRE 2016   DOI

36. Djamal Belazzougui, Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
    Lempel-Ziv Decoding in External Memory
    SEA 2016   DOI  |  Arxiv  |  Code

37. Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski
    Tighter Bounds for the Sum of Irreducible LCP Values
    CPM 2015   DOI

38. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
    Parallel External Memory Suffix Sorting
    CPM 2015   DOI  |  Code  |  Slides

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

40. Gabriele Fici, Travis Gagie, Juha Kärkkäinen, Dominik Kempa
    A Subquadratic Algorithm for Minimum Palindromic Factorization
    J. Discrete Algorithms 2014   DOI  |  Arxiv

41. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
    String Range Matching
    CPM 2014   DOI  |  Slides

42. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
    Lempel-Ziv Parsing in External Memory
    DCC 2014   DOI  |  Arxiv  |  Code  |  Poster  |  Slides

43. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
    Hybrid Compression of Bitvectors for the FM-Index
    DCC 2014   DOI  |  Code  |  Slides

44. Juha Kärkkäinen, Dominik Kempa
    Engineering a Lightweight External Memory Suffix Array Construction Algorithm
    ICABD 2014   DOI  |  Code

45. Tomohiro I, Juha Kärkkäinen, Dominik Kempa
    Faster Sparse Suffix Sorting
    STACS 2014   DOI

46. Juha Kärkkäinen, Dominik Kempa
    LCP Array Construction in External Memory
    SEA 2014   DOI  |  Code
    > Invited to ACM JEA Special Issue

47. Dominik Kempa, Simon J. Puglisi
    Lempel-Ziv Factorization: Simple, Fast, Practical
    ALENEX 2013   DOI  |  Code
    > Invited to ACM JEA Special Issue

48. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
    Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
    CPM 2013   DOI  |  Arxiv  |  Code  |  Slides

49. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
    Crochemore's String Matching Algorithm: Simplification, Extensions, Applications
    PSC 2013   DOI

50. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
    Lightweight Lempel-Ziv Parsing
    SEA 2013  DOI  |  Arxiv  |  Code

51. Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
    Slashing the Time for BWT Inversion
    DCC 2012   DOI  |  Poster

52. Juha Kärkkäinen, Pekka Mikkola, Dominik Kempa
    Grammar Precompression Speeds Up Burrows-Wheeler Compression
    SPIRE 2012   DOI  |  PDF