Tomasz Kociumaka

TK.jpg

Honors

2025 Presburger Award
2021 Cor Baayen Award
2018 Witold Lipski Prize

Short bio

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

2025

  1. Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
    Egor Gorbachev, and Tomasz Kociumaka
    57th Annual ACM Symposium on Theory of Computing, STOC 2025
  2. On the Hardness Hierarchy for the O(n √log n) Complexity in the Word RAM
    Dominik Kempa, and Tomasz Kociumaka
    57th Annual ACM Symposium on Theory of Computing, STOC 2025
  3. Pattern Matching under Weighted Edit Distance
    Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz
    66th Annual Symposium on Foundations of Computer Science, FOCS 2025
  4. Near-Optimal Property Testers for Pattern Matching
    Ce Jin, and Tomasz Kociumaka
    66th Annual Symposium on Foundations of Computer Science, FOCS 2025
  5. Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
    Debarati Das, Jacob Gilbert, Tomasz Kociumaka, MohammadTaghi Hajiaghayi, and Barna Saha
    66th Annual Symposium on Foundations of Computer Science, FOCS 2025

2024

  1. On the Communication Complexity of Approximate Pattern Matching
    Tomasz Kociumaka, Jakob Nogler, and Philip Wellnitz
    56th Annual ACM Symposium on Theory of Computing, STOC 2024
  2. LempelZiv (LZ77) Factorization in Sublinear Time
    Dominik Kempa, and Tomasz Kociumaka
    65th Annual Symposium on Foundations of Computer Science, FOCS 2024
  3. An Improved Algorithm for the k-Dyck Edit Distance Problem
    Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, and Tatiana Starikovskaya
    ACM Transactions on Algorithms
  4. Internal Pattern Matching Queries in a Text and Applications
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    SIAM Journal on Computing

2023

  1. Weighted Edit Distance Computation: Strings, Trees, and Dyck
    Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, and Barna Saha
    55th Annual ACM Symposium on Theory of Computing, STOC 2023
  2. Optimal Algorithms for Bounded Weighted Edit Distance
    Alejandro Cassis, Tomasz Kociumaka, and Philip Wellnitz
    64th Annual Symposium on Foundations of Computer Science, FOCS 2023
  3. Approximating Edit Distance in the Fully Dynamic Model
    Tomasz Kociumaka, Anish Mukherjee, and Barna Saha
    64th Annual Symposium on Foundations of Computer Science, FOCS 2023
  4. 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
  5. Toward a Definitive Compressibility Measure for Repetitive Sequences
    Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza
    IEEE Transactions on Information Theory

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 Goldenberg, Tomasz Kociumaka, Robert 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 Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, and Hamed Saleh
    63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
  4. Faster Pattern Matching under Edit Distance
    Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz
    63rd Annual Symposium on Foundations of Computer Science, FOCS 2022

2021

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

2020

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

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