Dominik Kempa

Assistant Professor
Department of Computer Science,
Stony Brook University

Email: lastname (at)
(replace lastname -> kempa)

Google Scholar


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). As an intern at Google, I worked on data compression. 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

  • Parallel and External-Memory Algorithms

Recent (+Selected) Publications

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

  • 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

  • Dominik Kempa, Nicola Prezza: At the Roots of Dictionary Compression: String Attractors, STOC 2018 DOI | Arxiv

  • Juha Kärkkäinen, Dominik Kempa: Better External Memory LCP Array Construction, ACM JEA 2019 DOI | Code

  • Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi, Bella Zhukova: Engineering External Memory Induced Suffix Sorting, ALENEX 2017 DOI | Code

Recent Teaching


Recent Talks