Dominik Kempa

Assistant Professor
Department of Computer Science
Stony Brook University, New York

Email: lastname (at) cs.stonybrook.edu
(replace lastname -> kempa)

Google Scholar

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 at the University of Helsinki, 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.

Research Interests


  • String Algorithms

  • Data Compression

  • Compressed Data Structures

  • Bioinformatics

  • Combinatorics on Words

  • Parallel and External-Memory Algorithms

Recent (+Selected) Publications

See the full list here (alternative: Google Scholar, DBLP).

  • Dominik Kempa, Tomasz Kociumaka: Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees, SODA 2023

  • 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

  • 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

  • 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 | Poster | Arxiv

News

  • 2022/10: Paper "Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees" with Tomasz Kociumaka accepted to SODA 2023.

  • 2022/10: I will give a keynote talk at SPIRE 2022!

  • 2022/10: 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

Recent Talks