Tomasz Kociumaka

ORCID

Publication Activity (10 Years)

Years Active: 2011-2024
Publications (10 Years): 193

Top Venues

Publications

Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz
On the Communication Complexity of Approximate Pattern Matching. STOC (2024)
Egor Gorbachev, Tomasz Kociumaka
Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights. CoRR (2024)
Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg
Dynamic Dynamic Time Warping. SODA (2024)
Tomasz Kociumaka, Gonzalo Navarro, Francisco Olivares
Near-Optimal Search Time in δ-Optimal Space, and Vice Versa. Algorithmica 86 (4) (2024)
Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz
On the Communication Complexity of Approximate Pattern Matching. CoRR (2024)
Daniel Gibney, Ce Jin, Tomasz Kociumaka, Sharma V. Thankachan
Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization. SODA (2024)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka
Faster Sublinear-Time Edit Distance. SODA (2024)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha
Brief Announcement: Upper and Lower Bounds for Edit Distance in Space-Efficient MPC. SPAA (2024)
Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, Tatiana Starikovskaya
-Dyck Edit Distance Problem. ACM Trans. Algorithms 20 (3) (2024)
Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl, Simon J. Puglisi
Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences. Algorithmica 86 (3) (2024)
Tomasz Kociumaka, Jakub Radoszewski, Tatiana Starikovskaya
Publisher Correction: Longest Common Substring with Approximately k Mismatches. Algorithmica 85 (10) (2023)
Dominik Kempa, Tomasz Kociumaka
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space. CoRR (2023)
Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg
Dynamic Dynamic Time Warping. CoRR (2023)
Alejandro Cassis, Tomasz Kociumaka, Philip Wellnitz
Optimal Algorithms for Bounded Weighted Edit Distance. CoRR (2023)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha
Weighted Edit Distance Computation: Strings, Trees, and Dyck. STOC (2023)
Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, Wiktor Zuba
Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String. CPM (2023)
Dominik Kempa, Tomasz Kociumaka
)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees. SODA (2023)
Gabriel Bathie, Tomasz Kociumaka, Tatiana Starikovskaya
Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares. CoRR (2023)
Gabriel Bathie, Tomasz Kociumaka, Tatiana Starikovskaya
Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares. ISAAC (2023)
Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka
Faster Sublinear-Time Edit Distance. CoRR (2023)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
An Algorithmic Bridge Between Hamming and Levenshtein Distances. ITCS (2023)
Tomasz Kociumaka, Adam Polak
Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths. ESA (2023)
Alejandro Cassis, Tomasz Kociumaka, Philip Wellnitz
Optimal Algorithms for Bounded Weighted Edit Distance. FOCS (2023)
Tomasz Kociumaka, Anish Mukherjee, Barna Saha
Approximating Edit Distance in the Fully Dynamic Model. CoRR (2023)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha
Weighted Edit Distance Computation: Strings, Trees and Dyck. CoRR (2023)
Tomasz Kociumaka, Anish Mukherjee, Barna Saha
Approximating Edit Distance in the Fully Dynamic Model. FOCS (2023)
Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen
Tight Bound for the Number of Distinct Palindromes in a Tree. Electron. J. Comb. 30 (2) (2023)
Dominik Kempa, Tomasz Kociumaka
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space. FOCS (2023)
Daniel Gibney, Ce Jin, Tomasz Kociumaka, Sharma V. Thankachan
Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization. CoRR (2023)
Tomasz Kociumaka, Gonzalo Navarro, Nicola Prezza
Toward a Definitive Compressibility Measure for Repetitive Sequences. IEEE Trans. Inf. Theory 69 (4) (2023)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
An Algorithmic Bridge Between Hamming and Levenshtein Distances. CoRR (2022)
Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, Tatiana Starikovskaya
An Improved Algorithm for The k-Dyck Edit Distance Problem. SODA (2022)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
Faster Pattern Matching under Edit Distance. CoRR (2022)
Debarati Das, Tomasz Kociumaka, Barna Saha
Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. ICALP (2022)
Tomasz Kociumaka, Gonzalo Navarro, Francisco Olivares
Near-Optimal Search Time in δ-Optimal Space. LATIN (2022)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
Faster Pattern Matching under Edit Distance : A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices. FOCS (2022)
Dominik Kempa, Tomasz Kociumaka
Resolution of the burrows-wheeler transform conjecture. Commun. ACM 65 (6) (2022)
Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha
How Compression and Approximation Affect Efficiency in String Distance Measures. SODA (2022)
Dominik Kempa, Tomasz Kociumaka
Dynamic suffix array with polylogarithmic queries and updates. STOC (2022)
Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya
Small-space and streaming pattern matching with $k$ edits. FOCS (2022)
Tomasz Kociumaka, Gonzalo Navarro, Francisco Olivares
Near-Optimal Search Time in δ-Optimal Space. CoRR (2022)
Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl, Simon J. Puglisi
Computing Longest (Common) Lyndon Subsequences. CoRR (2022)
Panagiotis Charalampopoulos, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Juliusz Straszynski
Efficient Computation of Sequence Mappability. Algorithmica 84 (5) (2022)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance. FOCS (2022)
Dominik Kempa, Tomasz Kociumaka
Dynamic Suffix Array with Polylogarithmic Queries and Updates. CoRR (2022)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Solon P. Pissis, Wojciech Rytter, Tomasz Walen, Wiktor Zuba
Approximate Circular Pattern Matching. ESA (2022)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance. CoRR (2022)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. FOCS (2022)
Raphaël Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski
The Dynamic k-Mismatch Problem. CPM (2022)
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba
Efficient representation and counting of antipower factors in words. Inf. Comput. 286 (2022)
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
A periodicity lemma for partial words. Inf. Comput. 283 (2022)
Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl, Simon J. Puglisi
Computing Longest (Common) Lyndon Subsequences. IWOCA (2022)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Solon P. Pissis, Wojciech Rytter, Tomasz Walen, Wiktor Zuba
Approximate Circular Pattern Matching. CoRR (2022)
Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha
How Compression and Approximation Affect Efficiency in String Distance Measures. CoRR (2021)
Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka, Gonzalo Navarro, Nicola Prezza
Optimal-Time Dictionary-Compressed Indexes. ACM Trans. Algorithms 17 (1) (2021)
Patrick Hagge Cording, Travis Gagie, Mathias Bæk Tejs Knudsen, Tomasz Kociumaka
Maximal unbordered factors of random strings. Theor. Comput. Sci. 852 (2021)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
Internal Dictionary Matching. Algorithmica 83 (7) (2021)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba
mismatches. J. Comput. Syst. Sci. 115 (2021)
Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya
Small-space and streaming pattern matching with $k$ edits. FOCS (2021)
Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya
Small space and streaming pattern matching with k edits. CoRR (2021)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. CoRR (2021)
Tomasz Kociumaka, Saeed Seddighin
Improved dynamic algorithms for longest increasing subsequence. STOC (2021)
Dominik Kempa, Tomasz Kociumaka
Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays. CoRR (2021)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski
Faster Algorithms for Longest Common Substring. CoRR (2021)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski
Faster Algorithms for Longest Common Substring. ESA (2021)
Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, Tatiana Starikovskaya
An Improved Algorithm for The k-Dyck Edit Distance Problem. CoRR (2021)
Debarati Das, Tomasz Kociumaka, Barna Saha
Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. CoRR (2021)
Raphaël Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski
The Dynamic k-Mismatch Problem. CoRR (2021)
Stav Ben-Nun, Shay Golan, Tomasz Kociumaka, Matan Kraus
Time-Space Tradeoffs for Finding a Long Common Substring. CoRR (2020)
Dominik Kempa, Tomasz Kociumaka
Resolution of the Burrows-Wheeler Transform Conjecture. FOCS (2020)
Patrick Dinklage, Johannes Fischer, Alexander Herlez, Tomasz Kociumaka, Florian Kurpicz
Practical Performance of Space Efficient Data Structures for Longest Common Extensions. ESA (2020)
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny M. Shur, Tomasz Walen
String periods in the order-preserving model. Inf. Comput. 270 (2020)
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Tatiana Starikovskaya
Approximating Longest Common Substring with k mismatches: Theory and Practice. CPM (2020)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
Faster Approximate Pattern Matching: A Unified Approach. CoRR (2020)
Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat
Approximating Text-to-Pattern Hamming Distances. CoRR (2020)
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat
The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time. CoRR (2020)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba
Counting Distinct Patterns in Internal Dictionary Matching. CPM (2020)
Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
A Linear-Time Algorithm for Seeds Computation. ACM Trans. Algorithms 16 (2) (2020)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, Wiktor Zuba
Efficient Enumeration of Distinct Factors Using Package Representations. SPIRE (2020)
Tomasz Kociumaka, Gonzalo Navarro, Nicola Prezza
Towards a Definitive Measure of Repetitiveness. LATIN (2020)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
Faster Approximate Pattern Matching: A Unified Approach. FOCS (2020)
Stav Ben-Nun, Shay Golan, Tomasz Kociumaka, Matan Kraus
Time-Space Tradeoffs for Finding a Long Common Substring. CPM (2020)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba
Counting Distinct Patterns in Internal Dictionary Matching. CoRR (2020)
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Tatiana Starikovskaya
Approximating longest common substring with $k$ mismatches: Theory and practice. CoRR (2020)
Tomasz Kociumaka, Barna Saha
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance. CoRR (2020)
Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat
Approximating text-to-pattern Hamming distances. STOC (2020)
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat
The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time. CPM (2020)
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, Przemyslaw Uznanski
Improved Circular k-Mismatch Sketches. CoRR (2020)
Tomasz Kociumaka, Barna Saha
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance. FOCS (2020)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Shay Mozes
Dynamic String Alignment. CPM (2020)
Carl Barton, Tomasz Kociumaka, Chang Liu, Solon P. Pissis, Jakub Radoszewski
Indexing weighted sequences: Neat and efficient. Inf. Comput. 270 (2020)
Pawel Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
Universal reconstruction of a string. Theor. Comput. Sci. 812 (2020)
Tomasz Kociumaka, Saeed Seddighin
Improved Dynamic Algorithms for Longest Increasing Subsequence. CoRR (2020)
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, Przemyslaw Uznanski
Improved Circular k-Mismatch Sketches. APPROX-RANDOM (2020)
Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen
Tight Bound for the Number of Distinct Palindromes in a Tree. CoRR (2020)
Evangelos Bampas, Jurek Czyzowicz, Leszek Gasieniec, David Ilcinkas, Ralf Klasing, Tomasz Kociumaka, Dominik Pajak
Linear Search by a Pair of Distinct-Speed Robots. Algorithmica 81 (1) (2019)
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat
Dynamic Dictionary Matching in the Online Model. WADS (2019)
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba
Weighted Shortest Common Supersequence Problem Revisited. SPIRE (2019)
Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba
Quasi-Linear-Time Algorithm for Longest Common Circular Factor. CoRR (2019)
Dominik Kempa, Tomasz Kociumaka
Resolution of the Burrows-Wheeler Transform Conjecture. CoRR (2019)

Tomasz Kociumaka.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Tomasz Kociumaka