Publications

Publications in reversed chronological order

2025

Conference Articles

  1. Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
    Tomasz Kociumaka, Jakob Nogler, and Philip Wellnitz
    36th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025
  2. 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
  3. 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

2024

Conference Articles

  1. Faster Sublinear-Time Edit Distance
    Karl Bringmann, Alejandro Cassis , Nick Fischer, and Tomasz Kociumaka
    35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
  2. Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel–Ziv Factorization
    Daniel Gibney, Ce Jin, Tomasz Kociumaka, and Sharma Thankachan
    35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
  3. Dynamic Dynamic Time Warping
    Karl Bringmann , Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, and Eva Rotenberg
    35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
  4. 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
  5. LempelZiv (LZ77) Factorization in Sublinear Time
    Dominik Kempa, and Tomasz Kociumaka
    65th Annual Symposium on Foundations of Computer Science, FOCS 2024
  6. Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts
    Anouk Duyster, and Tomasz Kociumaka
    String Processing and Information Retrieval, SPIRE 2024,

Journal Articles

  1. 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
  2. Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences
    Hideo Bannai,  Tomohiro I, Tomasz Kociumaka, Dominik Köppl, and Simon J. Puglisi
    Algorithmica
  3. Near-Optimal Search Time in δ-Optimal Space, and Vice Versa
    Tomasz Kociumaka, Gonzalo Navarro, and Francisco Olivares
    Algorithmica
  4. Internal Pattern Matching Queries in a Text and Applications
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    SIAM Journal on Computing

Miscellaneous

  1. Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
    Paweł Gawrychowski, Egor Gorbachev, and Tomasz Kociumaka

2023

Conference Articles

  1. An Algorithmic Bridge Between Hamming and Levenshtein Distances
    Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, and Barna Saha
    14th Innovations in Theoretical Computer Science Conference, ITCS 2023
  2. Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths
    Tomasz Kociumaka, and Adam Polak
    31st Annual European Symposium on Algorithms, ESA 2023
  3. Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees
    Dominik Kempa, and Tomasz Kociumaka
    34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
  4. Small-space algorithms for the online language distance problem for palindromes and squares
    Gabriel Bathie, Tomasz Kociumaka, and Tatiana Starikovskaya
    34th International Symposium on Algorithms and Computation, ISAAC 2023
  5. 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
  6. Optimal Algorithms for Bounded Weighted Edit Distance
    Alejandro Cassis, Tomasz Kociumaka, and Philip Wellnitz
    64th Annual Symposium on Foundations of Computer Science, FOCS 2023
  7. 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
  8. 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
  9. Linear Time Computation of Cyclic Roots and Cyclic Covers of a String
    Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba
    Combinatorial Pattern Matching, CPM 2023

Journal Articles

  1. Tight Bound for the Number of Distinct Palindromes in a Tree
    Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, and Tomasz Waleń
    Electronic Journal of Combinatorics
  2. Toward a Definitive Compressibility Measure for Repetitive Sequences
    Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza
    IEEE Transactions on Information Theory

2022

Conference Articles

  1. Approximate Circular Pattern Matching
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Solon P. Pissis, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba
    30th Annual European Symposium on Algorithms, ESA 2022
  2. Computing Longest (Common) Lyndon Subsequences
    Hideo Bannai,  Tomohiro I, Tomasz Kociumaka, Dominik Köppl, and Simon J. Puglisi
    33rd International Workshop on Combinatorial Algorithms, IWOCA 2022
  3. How Compression and Approximation Affect Efficiency in String Distance Measures
    Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, and Barna Saha
    33th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
  4. An Improved Algorithm for the k-Dyck Edit Distance Problem
    Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, and Tatiana Starikovskaya
    33th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
  5. Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding
    Debarati Das, Tomasz Kociumaka, and Barna Saha
    49th International Colloquium on Automata, Languages, and Programming, ICALP 2022
  6. Dynamic Suffix Array with Polylogarithmic Queries and Updates
    Dominik Kempa, and Tomasz Kociumaka
    54th Annual ACM Symposium on Theory of Computing, STOC 2022
  7. 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
  8. Õ(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
  9. Faster Pattern Matching under Edit Distance
    Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz
    63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
  10. The Dynamic k-Mismatch Problem
    Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, and Przemysław Uznański
    Combinatorial Pattern Matching, CPM 2022
  11. Near-Optimal Search Time in δ-Optimal Space
    Tomasz Kociumaka, Gonzalo Navarro, and Francisco Olivares
    Latin American Theoretical Informatics Symposium, LATIN 2022

Journal Articles

  1. Efficient computation of sequence mappability
    Panagiotis Charalampopoulos, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, and Juliusz Straszyński
    Algorithmica
  2. Resolution of the Burrows-Wheeler transform conjecture
    Dominik Kempa, and Tomasz Kociumaka
    Communications of the ACM
  3. A Periodicity Lemma for Partial Words
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Information and Computation
  4. Efficient representation and counting of antipower factors in words
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba
    Information and Computation

2021

Conference Articles

  1. Faster Algorithms for Longest Common Substring
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski
    29th Annual European Symposium on Algorithms, ESA 2021
  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 Kociumaka, Ely Porat, and Tatiana Starikovskaya
    62nd Annual Symposium on Foundations of Computer Science, FOCS 2021

Journal Articles

  1. Optimal-time dictionary-compressed indexes
    Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza
    ACM Transactions on Algorithms
  2. Internal Dictionary Matching
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Algorithmica
  3. Circular pattern matching with k mismatches
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba
    Journal of Computer and System Sciences
  4. Maximal unbordered factors of random strings
    Patrick Hagge Cording, Travis Gagie, Mathias Bæk Tejs Knudsen, and Tomasz Kociumaka
    Theoretical Computer Science

2020

Conference Articles

  1. Practical Performance of Space Efficient Data Structures for Longest Common Extensions
    Patrick Dinklage, Johannes Fischer, Alexander Herlez, Tomasz Kociumaka, and Florian Kurpicz
    28th Annual European Symposium on Algorithms, ESA 2020
  2. 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
  3. Faster Approximate Pattern Matching: A Unified Approach
    Panagiotis Charalampopoulos, Tomasz 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
  6. Improved Circular k-Mismatch Sketches
    Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, and Przemysław Uznański
    Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2020
  7. Approximating Longest Common Substring with k Mismatches: Theory and Practice
    Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, and Tatiana Starikovskaya
    Combinatorial Pattern Matching, CPM 2020
  8. Dynamic String Alignment
    Panagiotis Charalampopoulos, Tomasz Kociumaka, and Shay Mozes
    Combinatorial Pattern Matching, CPM 2020
  9. The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time
    Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat
    Combinatorial Pattern Matching, CPM 2020
  10. Time-Space Tradeoffs for Finding a Long Common Substring
    Stav Ben-Nun, Shay Golan, Tomasz Kociumaka, and Matan Kraus
    Combinatorial Pattern Matching, CPM 2020
  11. Counting Distinct Patterns in Internal Dictionary Matching
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba
    Combinatorial Pattern Matching, CPM 2020
  12. Towards a Definitive Measure of Repetitiveness
    Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza
    Latin American Theoretical Informatics Symposium, LATIN 2020
  13. Efficient Enumeration of Distinct Factors Using Package Representations
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba
    String Processing and Information Retrieval, SPIRE 2020

Journal Articles

  1. A linear time algorithm for seeds computation
    Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    ACM Transactions on Algorithms
  2. Indexing weighted sequences: Neat and efficient
    Carl Barton, Tomasz Kociumaka, Chang Liu, Solon P. Pissis, and Jakub Radoszewski
    Information and Computation
  3. String periods in the order-preserving model
    Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny Shur, and Tomasz Waleń
    Information and Computation
  4. Universal reconstruction of a string
    Paweł Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Theoretical Computer Science

2019

Conference Articles

  1. The streaming k-mismatch problem
    Raphaël Clifford, Tomasz Kociumaka, and Ely Porat
    30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
  2. Internal Dictionary Matching
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    30th International Symposium on Algorithms and Computation, ISAAC 2019
  3. 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
  4. Dynamic online dictionary matching
    Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat
    Algorithms and Data Structures, WADS 2019
  5. Graph and string Parameters: Connections between pathwidth, cutwidth and the locality number
    Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea, and Markus L. Schmid
    Automata, Languages, and Programming, ICALP 2019
  6. Quasi-linear-time algorithm for Longest Common Circular Factor
    Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba
    Combinatorial Pattern Matching, CPM 2019
  7. Circular pattern matching with k mismatches
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba
    Fundamentals of Computation Theory, FCT 2019
  8. Efficient representation and counting of antipower factors in words
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba
    Language and Automata Theory and Applications, LATA 2019
  9. RLE edit distance in near optimal time
    Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, and Przemysław Uznański
    Mathematical Foundations of Computer Science, MFCS 2019
  10. On Longest Common Property Preserved Substring Queries
    Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, and Tomasz Kociumaka
    String Processing and Information Retrieval, SPIRE 2019
  11. Weighted Shortest Common Supersequence Problem Revisited
    Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba
    String Processing and Information Retrieval, SPIRE 2019

Journal Articles

  1. Deleting Vertices to Graphs of Bounded Genus
    Tomasz Kociumaka, and Marcin Pilipczuk
    Algorithmica
  2. Longest common substring with approximately k mismatches
    Tomasz Kociumaka, Jakub Radoszewski, and Tatiana Starikovskaya
    Algorithmica
  3. Linear search by a pair of distinct-speed robots
    Evangelos Bampas, Jurek Czyżowicz, Leszek Gąsieniec, David Ilcinkas, Ralf Klasing, Tomasz Kociumaka, and Dominik Pająk
    Algorithmica
  4. Efficient enumeration of non-equivalent squares in partial words with few holes
    Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Journal of Combinatorial Optimization
  5. Pattern matching and consensus problems on weighted sequences and profiles
    Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski
    Theory of Computing Systems

2018

Conference Articles

  1. Edit distance with block operations
    Michał Gańczorz, Paweł Gawrychowski, Artur Jeż, and Tomasz Kociumaka
    26th Annual European Symposium on Algorithms, ESA 2018
  2. Optimal dynamic strings
    Paweł Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Łącki, and Piotr Sankowski
    29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
  3. Longest unbordered factor in quasilinear time
    Tomasz Kociumaka, Ritu Kundu, Manal Mohamed, and Solon P. Pissis
    29th International Symposium on Algorithms and Computation, ISAAC 2018
  4. Linear-time algorithm for Long LCF with k mismatches
    Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Combinatorial Pattern Matching, CPM 2018
  5. On periodicity lemma for partial words
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Language and Automata Theory and Applications, LATA 2018
  6. Faster recovery of approximate periods over edit distance
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba
    String Processing and Information Retrieval, SPIRE 2018
  7. Efficient computation of sequence mappability
    Mai Alzamel, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, and Juliusz Straszyński
    String Processing and Information Retrieval, SPIRE 2018
  8. String periods in the order-preserving model
    Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny Shur, and Tomasz Waleń
    Symposium on Theoretical Aspects of Computer Science, STACS 2018

Journal Articles

  1. On Abelian Longest Common Factor with and without RLE
    Szymon Grabowski, Tomasz Kociumaka, and Jakub Radoszewski
    Fundamenta Informaticae
  2. Efficient algorithms for shortest partial seeds in words
    Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Theoretical Computer Science
  3. On the string consensus problem and the Manhattan sequence consensus problem
    Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Theoretical Computer Science

2017

Conference Articles

  1. Sparse suffix tree construction in optimal time and space
    Paweł Gawrychowski, and Tomasz Kociumaka
    28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
  2. Efficient enumeration of non-equivalent squares in partial words with few holes
    Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Computing and Combinatorics, COCOON 2017
  3. On two LZ78-style grammars: compression bounds and compressed-space computation
    Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga, Tomasz Kociumaka, Dmitry Kosolobov, and Simon J. Puglisi
    String Processing and Information Retrieval, SPIRE 2017

Journal Articles

  1. Hardness of approximation for strip packing
    Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk , and Michał Pilipczuk
    ACM Transactions on Computation Theory
  2. Subquadratic-time algorithms for Abelian stringology problems
    Tomasz Kociumaka, Jakub Radoszewski, and Bartłomiej Wiśniewski
    AIMS Medical Science
  3. Efficient indexes for jumbled pattern matching with constant-sized alphabet
    Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter
    Algorithmica
  4. String powers in trees
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Algorithmica
  5. Fast algorithms for Abelian periods in words and greatest common divisor queries
    Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter
    Journal of Computer and System Sciences
  6. Covering problems for partial words and for indeterminate strings
    Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Theoretical Computer Science

2016

Conference Articles

  1. Pattern matching and consensus problems on weighted sequences and profiles
    Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski
    27th International Symposium on Algorithms and Computation, ISAAC 2016
  2. Efficient index for weighted sequences
    Carl Barton, Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski
    Combinatorial Pattern Matching, CPM 2016
  3. Faster Longest Common Extension queries in strings over general alphabets
    Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, and Tomasz Waleń
    Combinatorial Pattern Matching, CPM 2016
  4. Minimal suffix and rotation of a substring in optimal time
    Tomasz Kociumaka
    Combinatorial Pattern Matching, CPM 2016
  5. Near-optimal computation of runs over general alphabet via non-crossing LCE queries
    Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Ritu Kundu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    String Processing and Information Retrieval, SPIRE 2016
  6. Linear search by a pair of distinct-speed robots
    Evangelos Bampas, Jurek Czyżowicz, Leszek Gąsieniec, David Ilcinkas, Ralf Klasing, Tomasz Kociumaka, and Dominik Pająk
    Structural Information and Communication Complexity, SIROCCO 2016

Journal Articles

  1. On the greedy algorithm for the Shortest Common Superstring problem with reversals
    Gabriele Fici, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Information Processing Letters
  2. Efficient ranking of Lyndon words and decoding lexicographically minimal de Bruijn sequence
    Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter
    SIAM Journal on Discrete Mathematics
  3. Computing minimal and maximal suffixes of a substring
    Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka, Ignat Kolesnichenko, and Tatiana Starikovskaya
    Theoretical Computer Science
  4. Maximum number of distinct and nonequivalent nonstandard squares in a word
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Theoretical Computer Science
  5. Order-preserving indexing
    Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Theoretical Computer Science
  6. Fast computation of Abelian runs
    Gabriele Fici, Tomasz Kociumaka, Thierry Lecroq, Arnaud Lefebvre, and Élise Prieur-Gaston
    Theoretical Computer Science
  7. A fast branching algorithm for Cluster Vertex Deletion
    Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk
    Theory of Computing Systems

2015

Conference Articles

  1. Approximating LZ77 via small-space multiple-pattern matching
    Johannes Fischer, Travis Gagie, Paweł Gawrychowski, and Tomasz Kociumaka
    23rd Annual European Symposium on Algorithms, ESA 2015
  2. Wavelet trees meet suffix trees
    Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka, and Tatiana Starikovskaya
    26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
  3. Internal pattern matching queries in a text and applications
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
  4. Universal reconstruction of a string
    Paweł Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Algorithms and Data Structures, WADS 2015
  5. Approximating upper degree-constrained partial orientations
    Marek Cygan, and Tomasz Kociumaka
    Approximation, Randomization, and Combinatorial Optimization APPROX/RANDOM 2015
  6. String powers in trees
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Combinatorial Pattern Matching, CPM 2015
  7. Subquadratic-time algorithms for Abelian stringology problems
    Tomasz Kociumaka, Jakub Radoszewski, and Bartłomiej Wiśniewski
    Mathematical Aspects of Computer and Information Sciences, MACIS 2015
  8. Efficient algorithms for Longest Closed Factor array
    Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto, and Tomasz Waleń
    String Processing and Information Retrieval, SPIRE 2015
  9. Tight bound for the number of distinct palindromes in a tree
    Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, and Tomasz Waleń
    String Processing and Information Retrieval, SPIRE 2015

Journal Articles

  1. Fast algorithm for partial covers in words
    Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Algorithmica
  2. An LP-rounding 2√2-approximation for restricted maximum acyclic subgraph
    Fabrizio Grandoni, Tomasz Kociumaka, and Michał Włodarczyk
    Information Processing Letters
  3. A note on the longest common compatible prefix problem for partial words
    Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Jakub Radoszewski, Wojciech Rytter, Bartosz Szreder, and Tomasz Waleń
    Journal of Discrete Algorithms
  4. Linear-time version of Holub’s algorithm for morphic imprimitivity testing
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Theoretical Computer Science

2014

Conference Articles

  1. Sublinear space algorithms for the Longest Common Substring problem
    Tomasz Kociumaka, Tatiana Starikovskaya, and Hjalte Wedel Vildhøj
    22nd Annual European Symposium on Algorithms, ESA 2014
  2. Covering problems for partial words and for indeterminate strings
    Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Algorithms and Computation, ISAAC 2014
  3. Efficient algorithms for shortest partial seeds in words
    Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Combinatorial Pattern Matching, CPM 2014
  4. Computing kth Lyndon word and decoding lexicographically minimal de Bruijn sequence
    Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter
    Combinatorial Pattern Matching, CPM 2014
  5. Computing minimal and maximal suffixes of a substring revisited
    Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka, and Tatiana Starikovskaya
    Combinatorial Pattern Matching, CPM 2014
  6. A fast branching algorithm for Cluster Vertex Deletion
    Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, and Marcin Pilipczuk
    Computer Science Symposium in Russia, CSR 2014
  7. Maximum number of distinct and nonequivalent nonstandard squares in a word
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Developments in Language Theory, DLT 2014
  8. On the string consensus problem and the Manhattan sequence consensus problem
    Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    String Processing and Information Retrieval, SPIRE 2014
  9. Constant factor approximation for Capacitated k-Center with Outliers
    Marek Cygan, and Tomasz Kociumaka
    Symposium on Theoretical Aspects of Computer Science, STACS 2014

Journal Articles

  1. Faster deterministic Feedback Vertex Set
    Tomasz Kociumaka, and Marcin Pilipczuk
    Information Processing Letters
  2. Efficient counting of square substrings in a tree
    Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Theoretical Computer Science

2013

Conference Articles

  1. Efficient indexes for jumbled pattern matching with constant-sized alphabet
    Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter
    21st Annual European Symposium on Algorithms, ESA 2013
  2. Fast algorithm for partial covers in words
    Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Combinatorial Pattern Matching, CPM 2013
  3. Linear-time version of Holub’s algorithm for morphic imprimitivity testing
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    Language and Automata Theory and Applications, LATA 2013
  4. Order-preserving incomplete suffix trees and order-preserving indexes
    Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    String Processing and Information Retrieval, SPIRE 2013
  5. Fast algorithms for Abelian periods in words and greatest common divisor queries
    Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter
    Symposium on Theoretical Aspects of Computer Science, STACS 2013

Journal Articles

  1. A note on efficient computation of all Abelian periods in a string
    Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, Wojciech Tyczyński, and Tomasz Waleń
    Information Processing Letters
  2. Enhanced string covering
    Tomáš Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, William F. Smyth, and Wojciech Tyczyński
    Theoretical Computer Science

2012

Conference Articles

  1. A linear time algorithm for seeds computation
    Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
  2. Efficient counting of square substrings in a tree
    Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    23rd International Symposium on Algorithms and Computation, ISAAC 2012
  3. The maximum number of squares in a tree
    Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Wojciech Tyczyński, and Tomasz Waleń
    Combinatorial Pattern Matching, CPM 2012
  4. New and efficient approaches to the quasiperiodic characterisation of a string
    Tomáš Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, William F. Smyth, and Wojciech Tyczyński
    Prague Stringology Conference 2012
  5. Efficient data structures for the factor periodicity problem
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń
    String Processing and Information Retrieval, SPIRE 2012

Book Chapters

  1. Algorithmics of repetitions, local periods and critical factorization revisited
    Maxime Crochemore, Tomasz Kociumaka, Wojciech Rytter, Chalita Toopsuwan, Wojciech Tyczyński, and Tomasz Waleń
    Festschrift for Bořivoj Melichar