Dominik Kempa
Assistant Professor
Department of Computer Science
Stony Brook University, New York
Emails:
lastname (at) cs.stonybrook.edu
(fill in my lastname)
Embedded Files
About
I am an assistant professor in the Department of Computer Science at Stony Brook University. Prior to joining Stony Brook, I was a postdoc at Johns Hopkins University, where I was fortunate to be hosted by Ben Langmead. Before that, I was a postdoc at UC Berkeley (Theory group), lucky to be advised by Barna Saha. Even earlier, I held a postdoctoral position at the University of Warwick, gratefully following the guidance of Artur Czumaj.
I completed my PhD at the University of Helsinki, where I was extremely fortunate to be advised by Juha Kärkkäinen and Esko Ukkonen. Earlier, I was an intern at Google Zürich.
I obtained a BSc in Mathematics and an MSc in Computer Science from Jagiellonian University in Kraków. I am especially grateful to Maciej Ślusarek and Paweł Idziak for their support and guidance during my formative years.
Research Interests
String Algorithms
Data Compression
Compressed Data Structures
Combinatorics on Words
Parallel and External-Memory Algorithms
Recent Selected Publications
See the full list here (alternative: Google Scholar, DBLP).
SODA 2026: Dominik Kempa, Tomasz Kociumaka: Tight Lower Bounds for Central String Queries in Compressed Space Arxiv
SODA 2026: Dominik Kempa, Tomasz Kociumaka: Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries Arxiv
SODA 2026: Rajat De, Dominik Kempa: Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings Arxiv
STOC 2025: Dominik Kempa, Tomasz Kociumaka: On the Hardness Hierarchy for the O(n √log n) Complexity in the Word RAM DOI | Arxiv | Video (by Tomasz)
FOCS 2024: Dominik Kempa, Tomasz Kociumaka: Lempel-Ziv (LZ77) Factorization in Sublinear Time DOI | Arxiv | Video
SODA 2024: Rajat De, Dominik Kempa: Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data DOI | Arxiv
FOCS 2023: Dominik Kempa, Tomasz Kociumaka: Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space DOI | Arxiv
SODA 2023: Dominik Kempa, Tomasz Kociumaka: Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees DOI | Arxiv
STOC 2022: Dominik Kempa, Tomasz Kociumaka: Dynamic Suffix Array with Polylogarithmic Queries and Updates DOI | Arxiv
SODA 2022: Dominik Kempa, Barna Saha: An Upper Bound and Linear-Space Queries on the LZ-End Parsing DOI | Slides | Video
ESA 2021: Dominik Kempa, Ben Langmead: Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing DOI | Arxiv | Code | Slides | Video
FOCS 2020: Dominik Kempa, Tomasz Kociumaka: Resolution of the Burrows-Wheeler Transform Conjecture DOI | Arxiv | Slides | Video | ACM Highlight
STOC 2019: Dominik Kempa, Tomasz Kociumaka: String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure DOI | Poster | Arxiv
SODA 2019: Dominik Kempa: Optimal Construction of Compressed Indexes for Highly Repetitive Texts DOI | Arxiv
STOC 2018: Dominik Kempa, Nicola Prezza: At the Roots of Dictionary Compression: String Attractors DOI | Poster | Arxiv
Program Committees
News
2025/10: Papers "Tight Lower Bounds for Central String Queries in Compressed Space" and "Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries" with Tomasz Kociumaka, and "Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings" with Rajat De accepted to SODA 2026! Arxiv link 1 Arxiv link 2 Arxiv link 3
2025/08: Our STOC 2025 paper "On the Hardness Hierarchy for the O(n √log n) Complexity in the Word RAM" with Tomasz Kociumaka was invited to the Special Issue of SIAM Journal on Computing (SICOMP) for top STOC 2025 papers!
2025/04: Paper "On the Hardness Hierarchy for the O(n √log n) Complexity in the Word RAM" accepted to STOC 2025! DOI | Arxiv | Video (by Tomasz)
2025/03: I will be on the PC of DCC 2026.
2025/03: I will be on the PC of STACS 2026.
2024/09: Paper "Lempel-Ziv (LZ77) Factorization in Sublinear Time" accepted to FOCS 2024! DOI | Arxiv | Video
2024/08: I will be on the PC of: SODA 2025, DCC 2025, CPM 2025, SPIRE 2025, and SEA 2025.
2024/03: My project: "CAREER: Scalable and Flexible Indexing of Compressed Sequences" received an NSF CAREER award! See also: Department article | University article
2024/01: Paper "Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data" accepted to SODA 2024! DOI | Arxiv
2024/01: PC member and Special Session chair at Data Compression Conference 2024 (DCC 2024).
2023/08: Paper "Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space" accepted to FOCS 2023! DOI | Arxiv
2023/05: I will be on the PC of ALENEX 2024.
2023/02: I will be on the PC of ESA 2023 and SPIRE 2023.
2023/01: Paper "Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees" with Tomasz Kociumaka accepted to SODA 2023. DOI | Arxiv
2022/11: I will give a keynote talk at SPIRE 2022!
2022/11: I will be on the PC of CPM 2023.
2022/09: On Oct 13th I will give a talk about LZ-End parsing on the NYU Theory Seminar! Link
2022/06: Our paper "Resolution of the Burrows-Wheeler Transform Conjecture" with Tomasz Kociumaka featured in Research Highlights of Communications of the ACM! Introduction | Article | Department highlight
2022/03: Paper "Dynamic Suffix Array with Polylogarithmic Queries and Updates" with Tomasz Kociumaka accepted to STOC 2022. We propose the first dynamic suffix array that supports both queries and updates in O(polylog n) time! DOI | Arxiv
2022/02: Paper "An Upper Bound and Linear-Space Queries on the LZ-End Parsing" with Barna Saha accepted to SODA 2022 DOI | Slides | Video
2022/01: I will be on the PC of ESA 2022.
2021/12: I am on the Organizing Committee of the "Compression + Computation" workshop. I highly encourage registering and attending -- we have an excellent lineup of speakers and panelists! Link | Videos
2021/10: I will be on the PC of the 2022 Data Compression Conference (DCC 2022). I highly recommend submitting your work here! Call for papers. Submission deadline: Nov 8.
2021/10: I will be on the PC of CPM 2022. Call for papers.
2021/09: I started as an assistant professor in the Department of Computer Science at Stony Brook University!
2021/06: Paper "Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing" with Ben Langmead accepted to ESA 2021 DOI | Arxiv | Code | Slides | Video
2021/04: I will be on the PC of SPIRE 2021: Call for papers
2021/03: I will give a keynote talk at SEA 2021!
2021/01: Joined Langmead Lab at Johns Hopkins University!
2020/07: Paper accepted to FOCS 2020 Arxiv
2020/07: Github release of pSAscan, a parallel external-memory algorithm for suffix array construction
2020/07: Code release of fSAIS, and LZ-End parser
2020/06: Our STOC 2019 paper on String Synchronizing Sets and BWT construction featured in "Highlights of CPM" Link
2019/06: Invited talk about BWT in Dagstuhl Slides | Seminar
Recent Talks
Google Sites
Report abuse