Dominik Kempa
Assistant Professor
Department of Computer Science
Stony Brook University
Email: lastname (at) cs.stonybrook.edu
(replace lastname -> kempa)
Announcement: I am looking for Ph.D. student(s) in the area of string algorithms to start in the Fall '22. Please contact me by e-mail if you are interested (I strongly recommend reaching out to me by email early!). Please also have a look here (you need to formally apply to our program). Deadline: Jan 15.
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.
During my PhD, I implemented a collection of parallel and external-memory algorithms on strings (code: here or Github). Earlier, I was an intern in Google, Zürich. As an undergraduate, I enjoyed algorithm competitions (and practiced here). I am a recipient of the Junior Researcher Award and Outstanding Doctoral Dissertation Award. I obtained my MSc in Computer Science and BSc in Mathematics at Jagiellonian University.
Research Interests
String Algorithms
Data Compression
Compressed Data Structures
Bioinformatics
Parallel and External-Memory Algorithms
Recent (+Selected) Publications
See the full list here (alternative: Google Scholar, DBLP).
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
Dominik Kempa, Tomasz Kociumaka: String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure, STOC 2019 DOI | Arxiv
Dominik Kempa: Optimal Construction of Compressed Indexes for Highly Repetitive Texts, SODA 2019 DOI | Arxiv | Slides
Juha Kärkkäinen, Dominik Kempa: Better External Memory LCP Array Construction, ACM JEA 2019 DOI | Code
Dominik Kempa, Nicola Prezza: At the Roots of Dictionary Compression: String Attractors, STOC 2018 DOI | Arxiv
Code, Talks, and Writing
News
2022/01: New preprint: with Tomasz Kociumaka we propose the first dynamic suffix array that supports both queries and updates in O(polylog n) time! Arxiv
2022/01: I will be on the PC of ESA 2022 (Track B).
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
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: Paper "An Upper Bound and Linear-Space Queries on the LZ-End Parsing" with Barna Saha accepted to SODA 2022 DOI | Slides | Video
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 an invited 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
2020/05: I will be on the PC of CSR 2020
2019/06: Invited talk about BWT in Dagstuhl Slides | Seminar