Tomasz Kociumaka

I am a postdoc at the Max Planck Institute for Informatics, Germany, in the Algorithms and Complexity Department. Prior to that, I was a postdoc at University of California, Berkeley, hosted by Barna Saha, and at the Bar-Ilan Univeristy, Israel, hosted by Ely Porat. In 2019, I defended my PhD thesis at the University of Warsaw.

Contact

E-mail address: kociumaka@mimuw.edu.pl
Public PGP key

Papers

See also at DBLP and Google Scholar.
Order by
Filter

Faster Approximate Pattern Matching: A Unified Approach [DOI] [arXiv]
Panagiotis Charalampopoulos, Tomasz Kociumaka and Philip Wellnitz
61st Annual Symposium on Foundations of Computer Science, FOCS 2020

Resolution of the Burrows-Wheeler Transform Conjecture [DOI] [arXiv]
Dominik Kempa and Tomasz Kociumaka
61st Annual Symposium on Foundations of Computer Science, FOCS 2020

Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance [DOI] [arXiv]
Tomasz Kociumaka and Barna Saha
61st Annual Symposium on Foundations of Computer Science, FOCS 2020

Small space and streaming pattern matching with k edits [DOI] [arXiv]
Tomasz Kociumaka, Ely Porat and Tatiana Starikovskaya
62nd Annual Symposium on Foundations of Computer Science, FOCS 2021

Faster Pattern Matching under Edit Distance [DOI] [arXiv]
Panagiotis Charalampopoulos, Tomasz Kociumaka and Philip Wellnitz
63rd Annual Symposium on Foundations of Computer Science, FOCS 2022

O(n + poly(k))-time Algorithm for Bounded Tree Edit Distance [DOI] [arXiv]
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha and Hamed Saleh
63rd Annual Symposium on Foundations of Computer Science, FOCS 2022

Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal [DOI] [arXiv]
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer and Barna Saha
63rd Annual Symposium on Foundations of Computer Science, FOCS 2022

Optimal Algorithms for Bounded Weighted Edit Distance [arXiv]
Alejandro Cassis, Tomasz Kociumaka and Philip Wellnitz
64th Annual Symposium on Foundations of Computer Science, FOCS 2023

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space [arXiv]
Dominik Kempa and Tomasz Kociumaka
64th Annual Symposium on Foundations of Computer Science, FOCS 2023

Approximating Edit Distance in the Fully Dynamic Model [arXiv]
Tomasz Kociumaka, Anish Mukherjee and Barna Saha
64th Annual Symposium on Foundations of Computer Science, FOCS 2023

Subquadratic-time algorithms for Abelian stringology problems [DOI]
Tomasz Kociumaka, Jakub Radoszewski and Bartłomiej Wiśniewski
AIMS Medical Science

Linear search by a pair of distinct-speed robots [DOI]
Evangelos Bampas, Jurek Czyżowicz, Leszek Gąsieniec, David Ilcinkas, Ralf Klasing, Tomasz Kociumaka and Dominik Pająk
Algorithmica

Fast algorithm for partial covers in words [DOI] [arXiv]
Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Algorithmica

String powers in trees [DOI]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Algorithmica

Efficient indexes for jumbled pattern matching with constant-sized alphabet [DOI]
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter
Algorithmica

Deleting Vertices to Graphs of Bounded Genus [DOI] [arXiv]
Tomasz Kociumaka and Marcin Pilipczuk
Algorithmica

Longest common substring with approximately k mismatches [DOI] [arXiv]
Tomasz Kociumaka, Jakub Radoszewski and Tatiana Starikovskaya
Algorithmica

Internal Dictionary Matching [DOI] [arXiv]
Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Algorithmica

Efficient computation of sequence mappability [DOI] [arXiv]
Panagiotis Charalampopoulos, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski and Juliusz Straszyński
Algorithmica

Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences [DOI] [arXiv]
Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl and Simon J. Puglisi
Algorithmica

Approximating upper degree-constrained partial orientations [DOI] [arXiv] [pdf] [slides]
Marek Cygan and Tomasz Kociumaka
Approximation, Randomization, and Combinatorial Optimization APPROX/RANDOM 2015

Improved Circular k-Mismatch Sketches [DOI] [arXiv]
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat and Przemysław Uznański
Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2020

An Improved Algorithm for the k-Dyck Edit Distance Problem [DOI] [arXiv]
Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat and Tatiana Starikovskaya
33th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

How Compression and Approximation Affect Efficiency in String Distance Measures [DOI] [arXiv]
Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln and Barna Saha
33th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022

Approximating text-to-pattern Hamming distances [DOI] [arXiv]
Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz and Ely Porat
52nd Annual ACM Symposium on Theory of Computing, STOC 2020

Dynamic Suffix Array with Polylogarithmic Queries and Updates [DOI] [arXiv]
Dominik Kempa and Tomasz Kociumaka
54th Annual ACM Symposium on Theory of Computing, STOC 2022

Weighted Edit Distance Computation: Strings, Trees, and Dyck [arXiv]
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka and Barna Saha
55th Annual ACM Symposium on Theory of Computing, STOC 2023

Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding [DOI] [arXiv]
Debarati Das, Tomasz Kociumaka and Barna Saha
49th International Colloquium on Automata, Languages, and Programming, ICALP 2022

Resolution of the Burrows-Wheeler transform conjecture [DOI]
Dominik Kempa and Tomasz Kociumaka
Communications of the ACM

Efficient enumeration of non-equivalent squares in partial words with few holes [DOI] [pdf]
Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Computing and Combinatorics, COCOON 2017

The maximum number of squares in a tree [DOI] [pdf] [slides]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Wojciech Tyczyński and Tomasz Waleń
Combinatorial Pattern Matching, CPM 2012

Fast algorithm for partial covers in words [DOI] [pdf] [slides]
Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Combinatorial Pattern Matching, CPM 2013

Computing minimal and maximal suffixes of a substring revisited [DOI] [pdf]
Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka and Tatiana Starikovskaya
Combinatorial Pattern Matching, CPM 2014

Efficient algorithms for shortest partial seeds in words [DOI] [pdf] [slides]
Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Combinatorial Pattern Matching, CPM 2014

Computing kth Lyndon word and decoding lexicographically minimal de Bruijn sequence [DOI] [pdf] [slides]
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter
Combinatorial Pattern Matching, CPM 2014

String powers in trees [DOI] [pdf] [slides]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Combinatorial Pattern Matching, CPM 2015

Efficient index for weighted sequences [DOI] [arXiv] [slides]
Carl Barton, Tomasz Kociumaka, Solon P. Pissis and Jakub Radoszewski
Combinatorial Pattern Matching, CPM 2016

Faster Longest Common Extension queries in strings over general alphabets [DOI] [arXiv]
Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter and Tomasz Waleń
Combinatorial Pattern Matching, CPM 2016

Minimal suffix and rotation of a substring in optimal time [DOI] [arXiv] [slides]
Tomasz Kociumaka
Combinatorial Pattern Matching, CPM 2016

Linear-time algorithm for Long LCF with k mismatches [DOI] [arXiv]
Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Combinatorial Pattern Matching, CPM 2018

Quasi-linear-time algorithm for Longest Common Circular Factor [DOI] [arXiv]
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

Time-Space Tradeoffs for Finding a Long Common Substring [DOI] [arXiv]
Stav Ben-Nun, Shay Golan, Tomasz Kociumaka and Matan Kraus
Combinatorial Pattern Matching, CPM 2020

Dynamic String Alignment [DOI]
Panagiotis Charalampopoulos, Tomasz Kociumaka and Shay Mozes
Combinatorial Pattern Matching, CPM 2020

Counting Distinct Patterns in Internal Dictionary Matching [DOI] [arXiv]
Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń and Wiktor Zuba
Combinatorial Pattern Matching, CPM 2020

The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time [DOI] [arXiv]
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz and Ely Porat
Combinatorial Pattern Matching, CPM 2020

Approximating Longest Common Substring with k Mismatches: Theory and Practice [DOI] [arXiv]
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski and Tatiana Starikovskaya
Combinatorial Pattern Matching, CPM 2020

The Dynamic k-Mismatch Problem [DOI] [arXiv]
Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka, Daniel P. Martin and Przemysław Uznański
Combinatorial Pattern Matching, CPM 2022

A fast branching algorithm for Cluster Vertex Deletion [DOI] [pdf] [slides]
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka and Marcin Pilipczuk
Computer Science Symposium in Russia, CSR 2014

Maximum number of distinct and nonequivalent nonstandard squares in a word [DOI] [pdf]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Developments in Language Theory, DLT 2014

Tight Bound for the Number of Distinct Palindromes in a Tree [DOI] [arXiv]
Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter and Tomasz Waleń
Electronic Journal of Combinatorics

Efficient indexes for jumbled pattern matching with constant-sized alphabet [DOI] [pdf] [slides]
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter
21st Annual European Symposium on Algorithms, ESA 2013

Sublinear space algorithms for the Longest Common Substring problem [DOI] [arXiv] [pdf]
Tomasz Kociumaka, Tatiana Starikovskaya and Hjalte Wedel Vildhøj
22nd Annual European Symposium on Algorithms, ESA 2014

Approximating LZ77 via small-space multiple-pattern matching [DOI] [arXiv] [pdf]
Johannes Fischer, Travis Gagie, Paweł Gawrychowski and Tomasz Kociumaka
23rd Annual European Symposium on Algorithms, ESA 2015

Edit distance with block operations [DOI]
Michał Gańczorz, Paweł Gawrychowski, Artur Jeż and Tomasz Kociumaka
26th Annual European Symposium on Algorithms, ESA 2018

Practical Performance of Space Efficient Data Structures for Longest Common Extensions [DOI]
Patrick Dinklage, Johannes Fischer, Alexander Herlez, Tomasz Kociumaka and Florian Kurpicz
28th Annual European Symposium on Algorithms, ESA 2020

Faster Algorithms for Longest Common Substring [DOI] [arXiv]
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis and Jakub Radoszewski
29th Annual European Symposium on Algorithms, ESA 2021

Approximate Circular Pattern Matching [DOI] [arXiv]
Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Solon P. Pissis, Wojciech Rytter, Tomasz Waleń and Wiktor Zuba
30th Annual European Symposium on Algorithms, ESA 2022

Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths [DOI] [arXiv]
Tomasz Kociumaka and Adam Polak
31st Annual European Symposium on Algorithms, ESA 2023

Circular pattern matching with k mismatches [DOI] [arXiv]
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

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

On Abelian Longest Common Factor with and without RLE [DOI] [arXiv]
Szymon Grabowski, Tomasz Kociumaka and Jakub Radoszewski
Fundamenta Informaticae

Indexing weighted sequences: Neat and efficient [DOI] [arXiv]
Carl Barton, Tomasz Kociumaka, Chang Liu, Solon P. Pissis and Jakub Radoszewski
Information and Computation

String periods in the order-preserving model [DOI] [arXiv]
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny Shur and Tomasz Waleń
Information and Computation

A Periodicity Lemma for Partial Words [DOI] [arXiv]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Information and Computation

Efficient representation and counting of antipower factors in words [DOI] [arXiv]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń and Wiktor Zuba
Information and Computation

Graph and string Parameters: Connections between pathwidth, cutwidth and the locality number [DOI] [arXiv]
Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea and Markus L. Schmid
Automata, Languages, and Programming, ICALP 2019

A note on efficient computation of all Abelian periods in a string [DOI] [arXiv] [pdf]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, Wojciech Tyczyński and Tomasz Waleń
Information Processing Letters

On the greedy algorithm for the Shortest Common Superstring problem with reversals [DOI] [arXiv]
Gabriele Fici, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Information Processing Letters

An LP-rounding 22-approximation for restricted maximum acyclic subgraph [DOI] [arXiv] [pdf]
Fabrizio Grandoni, Tomasz Kociumaka and Michał Włodarczyk
Information Processing Letters

Faster deterministic Feedback Vertex Set [DOI] [arXiv] [pdf]
Tomasz Kociumaka and Marcin Pilipczuk
Information Processing Letters

Efficient counting of square substrings in a tree [DOI] [pdf]
Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
23rd International Symposium on Algorithms and Computation, ISAAC 2012

Covering problems for partial words and for indeterminate strings [DOI] [pdf] [slides]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Algorithms and Computation, ISAAC 2014

Pattern matching and consensus problems on weighted sequences and profiles [DOI] [slides]
Tomasz Kociumaka, Solon P. Pissis and Jakub Radoszewski
27th International Symposium on Algorithms and Computation, ISAAC 2016

Longest unbordered factor in quasilinear time [DOI] [arXiv]
Tomasz Kociumaka, Ritu Kundu, Manal Mohamed and Solon P. Pissis
29th International Symposium on Algorithms and Computation, ISAAC 2018

Internal Dictionary Matching [DOI]
Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
30th International Symposium on Algorithms and Computation, ISAAC 2019

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

An Algorithmic Bridge Between Hamming and Levenshtein Distances [DOI] [arXiv]
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer and Barna Saha
14th Innovations in Theoretical Computer Science Conference, ITCS 2023

Computing Longest (Common) Lyndon Subsequences [DOI] [arXiv]
Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl and Simon J. Puglisi
33rd International Workshop on Combinatorial Algorithms, IWOCA 2022

Fast algorithms for Abelian periods in words and greatest common divisor queries [DOI]
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter
Journal of Computer and System Sciences

Circular pattern matching with k mismatches [DOI] [arXiv]
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

A note on the longest common compatible prefix problem for partial words [DOI] [arXiv]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Jakub Radoszewski, Wojciech Rytter, Bartosz Szreder and Tomasz Waleń
Journal of Discrete Algorithms

Efficient enumeration of non-equivalent squares in partial words with few holes [DOI]
Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Journal of Combinatorial Optimization

Linear-time version of Holub's algorithm for morphic imprimitivity testing [DOI] [pdf]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Language and Automata Theory and Applications, LATA 2013

On periodicity lemma for partial words [DOI]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Language and Automata Theory and Applications, LATA 2018

Efficient representation and counting of antipower factors in words [DOI] [arXiv]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń and Wiktor Zuba
Language and Automata Theory and Applications, LATA 2019

Towards a Definitive Measure of Repetitiveness [DOI] [arXiv]
Tomasz Kociumaka, Gonzalo Navarro and Nicola Prezza
Latin American Theoretical Informatics Symposium, LATIN 2020

Near-Optimal Search Time in δ-Optimal Space [DOI] [arXiv]
Tomasz Kociumaka, Gonzalo Navarro and Francisco Olivares
Latin American Theoretical Informatics Symposium, LATIN 2022

Subquadratic-time algorithms for Abelian stringology problems [DOI]
Tomasz Kociumaka, Jakub Radoszewski and Bartłomiej Wiśniewski
Mathematical Aspects of Computer and Information Sciences, MACIS 2015

RLE edit distance in near optimal time [DOI] [arXiv]
Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka, Daniel P. Martin and Przemysław Uznański
Mathematical Foundations of Computer Science, MFCS 2019

New and efficient approaches to the quasiperiodic characterisation of a string [URL]
Tomáš Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, William F. Smyth and Wojciech Tyczyński
Prague Stringology Conference 2012

Efficient ranking of Lyndon words and decoding lexicographically minimal de Bruijn sequence [DOI] [arXiv]
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter
SIAM Journal on Discrete Mathematics

Linear search by a pair of distinct-speed robots [DOI]
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

A linear time algorithm for seeds computation [DOI] [slides]
Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Wavelet trees meet suffix trees [DOI] [arXiv] [slides]
Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka and Tatiana Starikovskaya
26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

Internal pattern matching queries in a text and applications [DOI] [arXiv] [slides]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

Sparse suffix tree construction in optimal time and space [DOI] [arXiv]
Paweł Gawrychowski and Tomasz Kociumaka
28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

Optimal dynamic strings [DOI] [arXiv] [slides]
Paweł Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Łącki and Piotr Sankowski
29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

The streaming k-mismatch problem [DOI] [arXiv] [slides]
Raphaël Clifford, Tomasz Kociumaka and Ely Porat
30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019

Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees [DOI] [arXiv]
Dominik Kempa and Tomasz Kociumaka
34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

Efficient data structures for the factor periodicity problem [DOI] [pdf] [slides]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
String Processing and Information Retrieval, SPIRE 2012

Order-preserving incomplete suffix trees and order-preserving indexes [DOI] [pdf]
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

On the string consensus problem and the Manhattan sequence consensus problem [DOI] [pdf]
Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
String Processing and Information Retrieval, SPIRE 2014

Efficient algorithms for Longest Closed Factor array [DOI] [pdf]
Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto and Tomasz Waleń
String Processing and Information Retrieval, SPIRE 2015

Tight bound for the number of distinct palindromes in a tree [DOI] [arXiv] [pdf]
Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter and Tomasz Waleń
String Processing and Information Retrieval, SPIRE 2015

Near-optimal computation of runs over general alphabet via non-crossing LCE queries [DOI] [arXiv] [slides]
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

On two LZ78-style grammars: compression bounds and compressed-space computation [DOI] [arXiv]
Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga, Tomasz Kociumaka, Dmitry Kosolobov and Simon J. Puglisi
String Processing and Information Retrieval, SPIRE 2017

Faster recovery of approximate periods over edit distance [DOI] [arXiv]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń and Wiktor Zuba
String Processing and Information Retrieval, SPIRE 2018

Efficient computation of sequence mappability [DOI] [arXiv]
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

Weighted Shortest Common Supersequence Problem Revisited [DOI] [arXiv]
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

On Longest Common Property Preserved Substring Queries [DOI] [arXiv]
Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda and Tomasz Kociumaka
String Processing and Information Retrieval, SPIRE 2019

Efficient Enumeration of Distinct Factors Using Package Representations [DOI] [pdf]
Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń and Wiktor Zuba
String Processing and Information Retrieval, SPIRE 2020

Fast algorithms for Abelian periods in words and greatest common divisor queries [DOI] [slides]
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter
Symposium on Theoretical Aspects of Computer Science, STACS 2013

Constant factor approximation for Capacitated k-Center with Outliers [DOI] [arXiv] [slides]
Marek Cygan and Tomasz Kociumaka
Symposium on Theoretical Aspects of Computer Science, STACS 2014

String periods in the order-preserving model [DOI]
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny Shur and Tomasz Waleń
Symposium on Theoretical Aspects of Computer Science, STACS 2018

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

Improved Dynamic Algorithms for Longest Increasing Subsequence [DOI] [arXiv]
Tomasz Kociumaka and Saeed Seddighin
53rd Annual ACM Symposium on Theory of Computing, STOC 2021

A linear time algorithm for seeds computation [DOI] [arXiv]
Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
ACM Transactions on Algorithms

Optimal-time dictionary-compressed indexes [DOI] [arXiv]
Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka, Gonzalo Navarro and Nicola Prezza
ACM Transactions on Algorithms

An Improved Algorithm for the k-Dyck Edit Distance Problem [DOI] [arXiv]
Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat and Tatiana Starikovskaya
ACM Transactions on Algorithms

Computing minimal and maximal suffixes of a substring [DOI] [arXiv]
Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka, Ignat Kolesnichenko and Tatiana Starikovskaya
Theoretical Computer Science

Maximal unbordered factors of random strings [DOI] [arXiv]
Patrick Hagge Cording, Travis Gagie, Mathias Bæk Tejs Knudsen and Tomasz Kociumaka
Theoretical Computer Science

Order-preserving indexing [DOI] [arXiv]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

Covering problems for partial words and for indeterminate strings [DOI] [arXiv]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

Fast computation of Abelian runs [DOI] [arXiv]
Gabriele Fici, Tomasz Kociumaka, Thierry Lecroq, Arnaud Lefebvre and Élise Prieur-Gaston
Theoretical Computer Science

Enhanced string covering [DOI] [arXiv]
Tomáš Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, William F. Smyth and Wojciech Tyczyński
Theoretical Computer Science

Universal reconstruction of a string [DOI]
Paweł Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

Efficient counting of square substrings in a tree [DOI] [pdf]
Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

Linear-time version of Holub's algorithm for morphic imprimitivity testing [DOI]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

Maximum number of distinct and nonequivalent nonstandard squares in a word [DOI] [arXiv]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

On the string consensus problem and the Manhattan sequence consensus problem [DOI] [arXiv]
Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

Efficient algorithms for shortest partial seeds in words [DOI]
Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

Toward a Definitive Compressibility Measure for Repetitive Sequences [DOI] [arXiv]
Tomasz Kociumaka, Gonzalo Navarro and Nicola Prezza
IEEE Transactions on Information Theory

A fast branching algorithm for Cluster Vertex Deletion [DOI] [arXiv]
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka and Marcin Pilipczuk
Theory of Computing Systems

Pattern matching and consensus problems on weighted sequences and profiles [DOI] [arXiv]
Tomasz Kociumaka, Solon P. Pissis and Jakub Radoszewski
Theory of Computing Systems

Hardness of approximation for strip packing [DOI] [arXiv]
Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk and Michał Pilipczuk
ACM Transactions on Computation Theory

Universal reconstruction of a string [DOI] [pdf] [slides]
Paweł Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Algorithms and Data Structures, WADS 2015

Dynamic online dictionary matching [DOI] [pdf]
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz and Ely Porat
Algorithms and Data Structures, WADS 2019

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