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 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 am a recipient of the Junior Researcher Award and the Outstanding Doctoral Dissertation Award.
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 Publications
See the full list here (alternative: Google Scholar, DBLP).
Dominik Kempa, Tomasz Kociumaka: On the Hardness Hierarchy for the O(n √log n) Complexity in the Word RAM, STOC 2025 DOI | Arxiv
Dominik Kempa, Tomasz Kociumaka: Lempel-Ziv (LZ77) Factorization in Sublinear Time, FOCS 2024 DOI | Arxiv | Video
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 | ACM Highlight
Dominik Kempa, Tomasz Kociumaka: String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure, STOC 2019 DOI | Poster | Arxiv
Dominik Kempa: Optimal Construction of Compressed Indexes for Highly Repetitive Texts, SODA 2019 DOI | Arxiv
Dominik Kempa, Nicola Prezza: At the Roots of Dictionary Compression: String Attractors, STOC 2018 DOI | Poster | Arxiv
Program Committees
News
2025/03: Paper "On the Hardness Hierarchy for the O(n √log n) Complexity in the Word RAM" accepted to STOC 2025! DOI | Arxiv
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