Tomasz Kociumaka
Publication record assembled from the DBLP archive of ranked conferences.
Papers indexed
109
Venues
20
Active years
2012–2026
Best venue rank
A*
Where they publish
Papers
109 indexed papers, newest first.
| Year | Venue | Title | Authors |
|---|---|---|---|
| 2026 | CPM | The Communication Complexity of Pattern Matching with Edits Revisited. | Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz |
| 2026 | ICALP | Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes. | Anouk Duyster, Tomasz Kociumaka |
| 2026 | SODA | Tight Lower Bounds for Central String Queries in Compressed Space. | Dominik Kempa, Tomasz Kociumaka |
| 2026 | SODA | Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries. | Dominik Kempa, Tomasz Kociumaka |
| 2026 | SODA | Space-Efficient k-Mismatch Text Indexes. | Tomasz Kociumaka, Jakub Radoszewski |
| 2026 | STACS | Time-Optimal Construction of String Synchronizing Sets. | Jonas Ellert, Tomasz Kociumaka |
| 2025 | ESA | Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds. | Itai Boneh, Egor Gorbachev, Tomasz Kociumaka |
| 2025 | ESA | Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications. | Pawel Gawrychowski, Egor Gorbachev, Tomasz Kociumaka |
| 2025 | ESA | Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime. | Tomasz Kociumaka, Ali Shahali |
| 2025 | FOCS | Pattern Matching under Weighted Edit Distance. | Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz |
| 2025 | FOCS | Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance. | Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha |
| 2025 | FOCS | Near-Optimal Property Testers for Pattern Matching. | Ce Jin, Tomasz Kociumaka |
| 2025 | SODA | Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching. | Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz |
| 2025 | STOC | Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights. | Egor Gorbachev, Tomasz Kociumaka |
| 2025 | STOC | On the Hardness Hierarchy for the O(n√log n) Complexity in the Word RAM. | Dominik Kempa, Tomasz Kociumaka |
| 2024 | FOCS | Lempel-Ziv (LZ77) Factorization in Sublinear Time. | Dominik Kempa, Tomasz Kociumaka |
| 2024 | SODA | Faster Sublinear-Time Edit Distance. | Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka |
| 2024 | SODA | Dynamic Dynamic Time Warping. | Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg |
| 2024 | SODA | Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization. | Daniel Gibney, Ce Jin, Tomasz Kociumaka, Sharma V. Thankachan |
| 2024 | STOC | On the Communication Complexity of Approximate Pattern Matching. | Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz |
| 2024 | SPAA | Brief Announcement: Upper and Lower Bounds for Edit Distance in Space-Efficient MPC. | Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha |
| 2024 | SPIRE | Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts. | Anouk Duyster, Tomasz Kociumaka |
| 2023 | CPM | Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String. | Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, Wiktor Zuba |
| 2023 | ESA | Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths. | Tomasz Kociumaka, Adam Polak |
| 2023 | FOCS | Optimal Algorithms for Bounded Weighted Edit Distance. | Alejandro Cassis, Tomasz Kociumaka, Philip Wellnitz |
| 2023 | FOCS | Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space. | Dominik Kempa, Tomasz Kociumaka |
| 2023 | FOCS | Approximating Edit Distance in the Fully Dynamic Model. | Tomasz Kociumaka, Anish Mukherjee, Barna Saha |
| 2023 | ISAAC | Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares. | Gabriel Bathie, Tomasz Kociumaka, Tatiana Starikovskaya |
| 2023 | SODA | Breaking the 𝒪( | Dominik Kempa, Tomasz Kociumaka |
| 2023 | STOC | Weighted Edit Distance Computation: Strings, Trees, and Dyck. | Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha |
| 2022 | CPM | The Dynamic k-Mismatch Problem. | Raphal Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski |
| 2022 | ESA | Approximate Circular Pattern Matching. | Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Solon P. Pissis, Wojciech Rytter, Tomasz Walen, Wiktor Zuba |
| 2022 | FOCS | (n+poly(k))-time Algorithm for Bounded Tree Edit Distance. | Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh |
| 2022 | FOCS | Faster Pattern Matching under Edit Distance : A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices. | Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz |
| 2022 | FOCS | Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. | Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha |
| 2022 | ICALP | Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. | Debarati Das, Tomasz Kociumaka, Barna Saha |
| 2022 | IWOCA | Computing Longest (Common) Lyndon Subsequences. | Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Kppl, Simon J. Puglisi |
| 2022 | LATIN | Near-Optimal Search Time in δ-Optimal Space. | Tomasz Kociumaka, Gonzalo Navarro, Francisco Olivares |
| 2022 | SODA | An Improved Algorithm for The k-Dyck Edit Distance Problem. | Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, Tatiana Starikovskaya |
| 2022 | SODA | How Compression and Approximation Affect Efficiency in String Distance Measures. | Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha |
| 2022 | STOC | Dynamic suffix array with polylogarithmic queries and updates. | Dominik Kempa, Tomasz Kociumaka |
| 2021 | ESA | Faster Algorithms for Longest Common Substring. | Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski |
| 2021 | FOCS | Small-space and streaming pattern matching with $k$ edits. | Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya |
| 2021 | STOC | Improved dynamic algorithms for longest increasing subsequence. | Tomasz Kociumaka, Saeed Seddighin |
| 2020 | CPM | Counting Distinct Patterns in Internal Dictionary Matching. | Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba |
| 2020 | CPM | Dynamic String Alignment. | Panagiotis Charalampopoulos, Tomasz Kociumaka, Shay Mozes |
| 2020 | CPM | The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time. | Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat |
| 2020 | CPM | Approximating Longest Common Substring with k mismatches: Theory and Practice. | Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Tatiana Starikovskaya |
| 2020 | CPM | Time-Space Tradeoffs for Finding a Long Common Substring. | Stav Ben-Nun, Shay Golan, Tomasz Kociumaka, Matan Kraus |
| 2020 | ESA | Practical Performance of Space Efficient Data Structures for Longest Common Extensions. | Patrick Dinklage, Johannes Fischer, Alexander Herlez, Tomasz Kociumaka, Florian Kurpicz |
| 2020 | FOCS | Faster Approximate Pattern Matching: A Unified Approach. | Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz |
| 2020 | FOCS | Resolution of the Burrows-Wheeler Transform Conjecture. | Dominik Kempa, Tomasz Kociumaka |
| 2020 | FOCS | Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance. | Tomasz Kociumaka, Barna Saha |
| 2020 | LATIN | Towards a Definitive Measure of Repetitiveness. | Tomasz Kociumaka, Gonzalo Navarro, Nicola Prezza |
| 2020 | STOC | Approximating text-to-pattern Hamming distances. | Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat |
| 2020 | SPIRE | Efficient Enumeration of Distinct Factors Using Package Representations. | Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, Wiktor Zuba |
| 2019 | CPM | Quasi-Linear-Time Algorithm for Longest Common Circular Factor. | Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba |
| 2019 | FCT | Circular Pattern Matching with k Mismatches. | Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba |
| 2019 | ICALP | Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number. | Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea, Markus L. Schmid |
| 2019 | ISAAC | Internal Dictionary Matching. | Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2019 | LATA | Efficient Representation and Counting of Antipower Factors in Words. | Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba |
| 2019 | MFCS | RLE Edit Distance in Near Optimal Time. | Raphal Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel P. Martin, Przemyslaw Uznanski |
| 2019 | SODA | The streaming k-mismatch problem. | Raphal Clifford, Tomasz Kociumaka, Ely Porat |
| 2019 | STOC | String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure. | Dominik Kempa, Tomasz Kociumaka |
| 2019 | SPIRE | Weighted Shortest Common Supersequence Problem Revisited. | Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba |
| 2019 | SPIRE | On Longest Common Property Preserved Substring Queries. | Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tomasz Kociumaka |
| 2019 | WADS | Dynamic Dictionary Matching in the Online Model. | Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat |
| 2018 | CPM | 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, Tomasz Walen |
| 2018 | ESA | Edit Distance with Block Operations. | Michal Ganczorz, Pawel Gawrychowski, Artur Jez, Tomasz Kociumaka |
| 2018 | ISAAC | Longest Unbordered Factor in Quasilinear Time. | Tomasz Kociumaka, Ritu Kundu, Manal Mohamed, Solon P. Pissis |
| 2018 | LATA | On Periodicity Lemma for Partial Words. | Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2018 | SODA | Optimal Dynamic Strings. | Pawel Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Lacki, Piotr Sankowski |
| 2018 | STACS | String Periods in the Order-Preserving Model. | Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny M. Shur, Tomasz Walen |
| 2018 | SPIRE | Efficient Computation of Sequence Mappability. | Mai Alzamel, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Juliusz Straszynski |
| 2018 | SPIRE | Faster Recovery of Approximate Periods over Edit Distance. | Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba |
| 2017 | COCOON | 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, Tomasz Walen |
| 2017 | SODA | Sparse Suffix Tree Construction in Optimal Time and Space. | Pawel Gawrychowski, Tomasz Kociumaka |
| 2017 | SPIRE | On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation. | Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga, Tomasz Kociumaka, Dmitry Kosolobov, Simon J. Puglisi |
| 2016 | CPM | Efficient Index for Weighted Sequences. | Carl Barton, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski |
| 2016 | CPM | Faster Longest Common Extension Queries in Strings over General Alphabets. | Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen |
| 2016 | CPM | Minimal Suffix and Rotation of a Substring in Optimal Time. | Tomasz Kociumaka |
| 2016 | ISAAC | Pattern Matching and Consensus Problems on Weighted Sequences and Profiles. | Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski |
| 2016 | SIROCCO | Linear Search by a Pair of Distinct-Speed Robots. | Evangelos Bampas, Jurek Czyzowicz, Leszek Gasieniec, David Ilcinkas, Ralf Klasing, Tomasz Kociumaka, Dominik Pajak |
| 2016 | SPIRE | 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, Tomasz Walen |
| 2015 | CPM | String Powers in Trees. | Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2015 | ESA | Approximating LZ77 via Small-Space Multiple-Pattern Matching. | Johannes Fischer, Travis Gagie, Pawel Gawrychowski, Tomasz Kociumaka |
| 2015 | SODA | Wavelet Trees Meet Suffix Trees. | Maxim A. Babenko, Pawel Gawrychowski, Tomasz Kociumaka, Tatiana Starikovskaya |
| 2015 | SODA | Internal Pattern Matching Queries in a Text and Applications. | Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2015 | SPIRE | Efficient Algorithms for Longest Closed Factor Array. | Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto, Tomasz Walen |
| 2015 | SPIRE | Tight Bound for the Number of Distinct Palindromes in a Tree. | Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen |
| 2015 | WADS | Universal Reconstruction of a String. | Pawel Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2014 | CPM | Computing Minimal and Maximal Suffixes of a Substring Revisited. | Maxim A. Babenko, Pawel Gawrychowski, Tomasz Kociumaka, Tatiana Starikovskaya |
| 2014 | CPM | Efficient Algorithms for Shortest Partial Seeds in Words. | Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2014 | CPM | Computing k-th Lyndon Word and Decoding Lexicographically Minimal de Bruijn Sequence. | Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter |
| 2014 | CSR | A Fast Branching Algorithm for Cluster Vertex Deletion. | Anudhyan Boral, Marek Cygan, Tomasz Kociumaka, Marcin Pilipczuk |
| 2014 | DLT | Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word. | Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2014 | ESA | Sublinear Space Algorithms for the Longest Common Substring Problem. | Tomasz Kociumaka, Tatiana Starikovskaya, Hjalte Wedel Vildhj |
| 2014 | ISAAC | Covering Problems for Partial Words and for Indeterminate Strings. | Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2014 | STACS | Constant Factor Approximation for Capacitated k-Center with Outliers. | Marek Cygan, Tomasz Kociumaka |
| 2014 | SPIRE | On the String Consensus Problem and the Manhattan Sequence Consensus Problem. | Tomasz Kociumaka, Jakub W. Pachocki, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2013 | CPM | Fast Algorithm for Partial Covers in Words. | Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2013 | ESA | Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet. | Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter |
| 2013 | LATA | Linear-Time Version of Holub's Algorithm for Morphic Imprimitivity Testing. | Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2013 | STACS | Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries. | Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter |
| 2013 | SPIRE | 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, Tomasz Walen |
| 2012 | CPM | The Maximum Number of Squares in a Tree. | Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Wojciech Tyczynski, Tomasz Walen |
| 2012 | ISAAC | Efficient Counting of Square Substrings in a Tree. | Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2012 | SODA | A linear time algorithm for seeds computation. | Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2012 | SPIRE | Efficient Data Structures for the Factor Periodicity Problem. | Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |