Dominik Kempa
Assistant Professor
Department of Computer Science
Stony Brook University, New York
Email: lastname (at) cs.stonybrook.edu
(replace lastname -> kempa)
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 fortunate to be hosted by Ben Langmead, and before that at UC Berkeley (Theory group), lucky to be advised by Barna Saha. Even before that I was a postdoc at the University of Warwick, under the watchful eye of Artur Czumaj.
I did my PhD at the University of Helsinki, where I was advised by Juha Kärkkäinen and Esko Ukkonen. Earlier, I was an intern in Google, Zürich. I obtained a BSc in Mathematics and MSc in Computer Science (advised by Maciej Slusarek) at Jagiellonian University in Poland. I am a recipient of the Junior Researcher Award and Outstanding Doctoral Dissertation Award.
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: Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space, FOCS 2023 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
News
2023/08: Paper "Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space" accepted to FOCS 2023! Arxiv
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: I am deeply honored to have 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