Tomasz Kociumaka

Max Planck Institute for Informatics, Department 1: Algorithms and Complexity.

TK.jpg

Research interests

My research revolves around designing efficient algorithms for processing strings (texts, sequences) with a particular focus on sequence similarity measures, approximate pattern matching, lossless data compression, and text indexing data structures. I study string problems from multiple perspectives, including fine-grained complexity, dynamic algorithms, streaming, sketching, sublinear algorithms, and quantum computing.

Selected publications

2023

  1. Toward a Definitive Compressibility Measure for Repetitive Sequences
    Tomasz KociumakaGonzalo Navarro, and Nicola Prezza
    IEEE Transactions on Information Theory
  2. Weighted Edit Distance Computation: Strings, Trees, and Dyck
    55th Annual ACM Symposium on Theory of Computing, STOC 2023
  3. Optimal Algorithms for Bounded Weighted Edit Distance
    Alejandro CassisTomasz Kociumaka, and Philip Wellnitz
    64th Annual Symposium on Foundations of Computer Science, FOCS 2023
  4. Approximating Edit Distance in the Fully Dynamic Model
    Tomasz KociumakaAnish Mukherjee, and Barna Saha
    64th Annual Symposium on Foundations of Computer Science, FOCS 2023
  5. Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
    Dominik Kempa, and Tomasz Kociumaka
    64th Annual Symposium on Foundations of Computer Science, FOCS 2023
  6. An Improved Algorithm for the k-Dyck Edit Distance Problem
    Dvir Fried, Shay GolanTomasz KociumakaTsvi KopelowitzEly Porat, and Tatiana Starikovskaya
    ACM Transactions on Algorithms

2022

  1. Dynamic Suffix Array with Polylogarithmic Queries and Updates
    Dominik Kempa, and Tomasz Kociumaka
    54th Annual ACM Symposium on Theory of Computing, STOC 2022
  2. Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
    Elazar GoldenbergTomasz KociumakaRobert Krauthgamer, and Barna Saha
    63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
  3. Õ(n + poly(k))-time Algorithm for Bounded Tree Edit Distance
    Debarati DasJacob GilbertMohammadTaghi HajiaghayiTomasz KociumakaBarna Saha, and Hamed Saleh
    63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
  4. Faster Pattern Matching under Edit Distance
    Panagiotis CharalampopoulosTomasz Kociumaka, and Philip Wellnitz
    63rd Annual Symposium on Foundations of Computer Science, FOCS 2022

2021

  1. Optimal-time dictionary-compressed indexes
    Anders Roy Christiansen, Mikko Berggren EttienneTomasz KociumakaGonzalo Navarro, and Nicola Prezza
    ACM Transactions on Algorithms
  2. Improved Dynamic Algorithms for Longest Increasing Subsequence
    Tomasz Kociumaka, and Saeed Seddighin
    53rd Annual ACM Symposium on Theory of Computing, STOC 2021
  3. Small space and streaming pattern matching with k edits
    Tomasz KociumakaEly Porat, and Tatiana Starikovskaya
    62nd Annual Symposium on Foundations of Computer Science, FOCS 2021

2020

  1. A linear time algorithm for seeds computation
    ACM Transactions on Algorithms
  2. Approximating text-to-pattern Hamming distances
    Timothy M. ChanShay GolanTomasz KociumakaTsvi Kopelowitz, and Ely Porat
    52nd Annual ACM Symposium on Theory of Computing, STOC 2020
  3. Faster Approximate Pattern Matching: A Unified Approach
    Panagiotis CharalampopoulosTomasz Kociumaka, and Philip Wellnitz
    61st Annual Symposium on Foundations of Computer Science, FOCS 2020
  4. Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance
    Tomasz Kociumaka, and Barna Saha
    61st Annual Symposium on Foundations of Computer Science, FOCS 2020
  5. Resolution of the Burrows-Wheeler Transform Conjecture
    Dominik Kempa, and Tomasz Kociumaka
    61st Annual Symposium on Foundations of Computer Science, FOCS 2020

2019

  1. String synchronizing sets: Sublinear-time BWT construction and optimal LCE data structure
    Dominik Kempa, and Tomasz Kociumaka
    51st Annual ACM Symposium on Theory of Computing, STOC 2019