Tomasz Kociumaka

I am a postdoc in the Department of Computer Science at Bar-Ilan Univeristy, Isreal. In September 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

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

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

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

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

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

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

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

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

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

Edit distance with block operations [DOI]
Michał Gańczorz, Paweł Gawrychowski, Artur Jeż and Tomasz Kociumaka
Algorithms --- ESA 2018

Efficient counting of square substrings in a tree [DOI] [pdf]
Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
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] [arXiv] [slides]
Tomasz Kociumaka, Solon P. Pissis and Jakub Radoszewski
Algorithms and Computation, ISAAC 2016

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

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

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

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

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

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

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

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

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

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

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

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]
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny Shur and Tomasz Waleń
Information and Computation

On periodicity lemma for partial words
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Information and Computation

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 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

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

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

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] [arXiv]
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 [arXiv]
Tomasz Kociumaka, Gonzalo Navarro and Nicola Prezza
Latin American Theoretical Informatics Symposium, LATIN 2020

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

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] [arXiv] [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] [arXiv] [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] [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

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

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] [arXiv]
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny Shur and Tomasz Waleń
Symposium on Theoretical Aspects of Computer Science, STACS 2018

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

Order-preserving indexing [DOI]
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]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

On the string consensus problem and the Manhattan sequence consensus problem [DOI]
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

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]
Tomasz Kociumaka, Solon P. Pissis and Jakub Radoszewski
Theory of Computing Systems

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

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