Tomasz Kociumaka

Affiliations:
  • Max Planck Institute for Informatics, Saarbrücken, Germany
  • University of Warsaw, Poland (former)


According to our database1, Tomasz Kociumaka authored at least 125 papers between 2012 and 2023.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Publisher Correction: Longest Common Substring with Approximately k Mismatches.
Algorithmica, October, 2023

Toward a Definitive Compressibility Measure for Repetitive Sequences.
IEEE Trans. Inf. Theory, April, 2023

Faster Sublinear-Time Edit Distance.
CoRR, 2023

Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization.
CoRR, 2023

Dynamic Dynamic Time Warping.
CoRR, 2023

Tight Bound for the Number of Distinct Palindromes in a Tree.
Electron. J. Comb., 2023

Weighted Edit Distance Computation: Strings, Trees, and Dyck.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Breaking the 𝒪(<i>n</i>)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares.
Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

An Algorithmic Bridge Between Hamming and Levenshtein Distances.
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Approximating Edit Distance in the Fully Dynamic Model.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Optimal Algorithms for Bounded Weighted Edit Distance.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths.
Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String.
Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching, 2023

2022
A periodicity lemma for partial words.
Inf. Comput., 2022

Efficient representation and counting of antipower factors in words.
Inf. Comput., 2022

Faster Pattern Matching under Edit Distance.
CoRR, 2022

Resolution of the burrows-wheeler transform conjecture.
Commun. ACM, 2022

Efficient Computation of Sequence Mappability.
Algorithmica, 2022

Dynamic suffix array with polylogarithmic queries and updates.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

How Compression and Approximation Affect Efficiency in String Distance Measures.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

An Improved Algorithm for The k-Dyck Edit Distance Problem.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Near-Optimal Search Time in δ-Optimal Space.
Proceedings of the LATIN 2022: Theoretical Informatics, 2022

Computing Longest (Common) Lyndon Subsequences.
Proceedings of the Combinatorial Algorithms - 33rd International Workshop, 2022

Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Faster Pattern Matching under Edit Distance : A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Approximate Circular Pattern Matching.
Proceedings of the 30th Annual European Symposium on Algorithms, 2022

The Dynamic k-Mismatch Problem.
Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching, 2022

2021
Maximal unbordered factors of random strings.
Theor. Comput. Sci., 2021

Optimal-Time Dictionary-Compressed Indexes.
ACM Trans. Algorithms, 2021

Circular pattern matching with <i>k</i> mismatches.
J. Comput. Syst. Sci., 2021

Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays.
CoRR, 2021

Internal Dictionary Matching.
Algorithmica, 2021

Improved dynamic algorithms for longest increasing subsequence.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Small-space and streaming pattern matching with $k$ edits.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Faster Algorithms for Longest Common Substring.
Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020
Universal reconstruction of a string.
Theor. Comput. Sci., 2020

A Linear-Time Algorithm for Seeds Computation.
ACM Trans. Algorithms, 2020

String periods in the order-preserving model.
Inf. Comput., 2020

Indexing weighted sequences: Neat and efficient.
Inf. Comput., 2020

Approximating text-to-pattern Hamming distances.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Efficient Enumeration of Distinct Factors Using Package Representations.
Proceedings of the String Processing and Information Retrieval, 2020

Towards a Definitive Measure of Repetitiveness.
Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Faster Approximate Pattern Matching: A Unified Approach.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Time-Space Tradeoffs for Finding a Long Common Substring.
Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

Approximating Longest Common Substring with k mismatches: Theory and Practice.
Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time.
Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

Dynamic String Alignment.
Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

Counting Distinct Patterns in Internal Dictionary Matching.
Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

Improved Circular k-Mismatch Sketches.
Proceedings of the Approximation, 2020

2019
Pattern Matching and Consensus Problems on Weighted Sequences and Profiles.
Theory Comput. Syst., 2019

Efficient enumeration of non-equivalent squares in partial words with few holes.
J. Comb. Optim., 2019

Correction to: Longest Common Substring with Approximately k Mismatches.
Algorithmica, 2019

Longest Common Substring with Approximately k Mismatches.
Algorithmica, 2019

Deleting Vertices to Graphs of Bounded Genus.
Algorithmica, 2019

Linear Search by a Pair of Distinct-Speed Robots.
Algorithmica, 2019

Dynamic Dictionary Matching in the Online Model.
Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

On Longest Common Property Preserved Substring Queries.
Proceedings of the String Processing and Information Retrieval, 2019

Weighted Shortest Common Supersequence Problem Revisited.
Proceedings of the String Processing and Information Retrieval, 2019

The streaming k-mismatch problem.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

RLE Edit Distance in Near Optimal Time.
Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Circular Pattern Matching with k Mismatches.
Proceedings of the Fundamentals of Computation Theory - 22nd International Symposium, 2019

Quasi-Linear-Time Algorithm for Longest Common Circular Factor.
Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, 2019

2018
Efficient algorithms for shortest partial seeds in words.
Theor. Comput. Sci., 2018

On the string consensus problem and the Manhattan sequence consensus problem.
Theor. Comput. Sci., 2018

On Abelian Longest Common Factor with and without RLE.
Fundam. Informaticae, 2018

Faster Recovery of Approximate Periods over Edit Distance.
Proceedings of the String Processing and Information Retrieval, 2018

Efficient Computation of Sequence Mappability.
Proceedings of the String Processing and Information Retrieval, 2018

Optimal Dynamic Strings.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Longest Unbordered Factor in Quasilinear Time.
Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

How Much Different Are Two Words with Different Shortest Periods.
Proceedings of the Artificial Intelligence Applications and Innovations, 2018

Edit Distance with Block Operations.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Linear-Time Algorithm for Long LCF with k Mismatches.
Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

2017
Hardness of Approximation for Strip Packing.
ACM Trans. Comput. Theory, 2017

Covering problems for partial words and for indeterminate strings.
Theor. Comput. Sci., 2017

Fast algorithms for Abelian periods in words and greatest common divisor queries.
J. Comput. Syst. Sci., 2017

String Powers in Trees.
Algorithmica, 2017

Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet.
Algorithmica, 2017

On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation.
Proceedings of the String Processing and Information Retrieval, 2017

Sparse Suffix Tree Construction in Optimal Time and Space.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016
Maximum number of distinct and nonequivalent nonstandard squares in a word.
Theor. Comput. Sci., 2016

Fast computation of abelian runs.
Theor. Comput. Sci., 2016

Order-preserving indexing.
Theor. Comput. Sci., 2016

Computing minimal and maximal suffixes of a substring.
Theor. Comput. Sci., 2016

Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence.
SIAM J. Discret. Math., 2016

A Fast Branching Algorithm for Cluster Vertex Deletion.
Theory Comput. Syst., 2016

On the greedy algorithm for the Shortest Common Superstring problem with reversals.
Inf. Process. Lett., 2016

Parameterizing PWM- and Profile-Matching and Knapsack by the feasible-weight solutions count.
CoRR, 2016

Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries.
Proceedings of the String Processing and Information Retrieval, 2016

Minimal Suffix and Rotation of a Substring in Optimal Time.
Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

Faster Longest Common Extension Queries in Strings over General Alphabets.
Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

Efficient Index for Weighted Sequences.
Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

2015
Linear-time version of Holub's algorithm for morphic imprimitivity testing.
Theor. Comput. Sci., 2015

A note on the longest common compatible prefix problem for partial words.
J. Discrete Algorithms, 2015

An LP-rounding 2√2-approximation for restricted maximum acyclic subgraph.
Inf. Process. Lett., 2015

Fast Algorithm for Partial Covers in Words.
Algorithmica, 2015

Efficient Algorithms for Longest Closed Factor Array.
Proceedings of the String Processing and Information Retrieval, 2015

Internal Pattern Matching Queries in a Text and Applications.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Wavelet Trees Meet Suffix Trees.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Subquadratic-Time Algorithms for Abelian Stringology Problems.
Proceedings of the Mathematical Aspects of Computer and Information Sciences, 2015

Approximating LZ77 via Small-Space Multiple-Pattern Matching.
Proceedings of the Algorithms - ESA 2015, 2015

Approximating Upper Degree-Constrained Partial Orientations.
Proceedings of the Approximation, 2015

2014
Efficient counting of square substrings in a tree.
Theor. Comput. Sci., 2014

Faster deterministic Feedback Vertex Set.
Inf. Process. Lett., 2014

An LP-Rounding $2\sqrt{2}$ Approximation for Restricted Maximum Acyclic Subgraph.
CoRR, 2014

Constant Factor Approximation for Capacitated k-Center with Outliers.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Sublinear Space Algorithms for the Longest Common Substring Problem.
Proceedings of the Algorithms - ESA 2014, 2014

Computing k-th Lyndon Word and Decoding Lexicographically Minimal de Bruijn Sequence.
Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

Computing Minimal and Maximal Suffixes of a Substring Revisited.
Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

2013
Enhanced string covering.
Theor. Comput. Sci., 2013

A note on efficient computation of all Abelian periods in a string.
Inf. Process. Lett., 2013

Order-Preserving Suffix Trees and Their Algorithmic Applications
CoRR, 2013

Optimal Data Structure for Internal Pattern Matching Queries in a Text and Applications.
CoRR, 2013

Substring Suffix Selection.
CoRR, 2013

Order-Preserving Incomplete Suffix Trees and Order-Preserving Indexes.
Proceedings of the String Processing and Information Retrieval, 2013

2012
New and Efficient Approaches to the Quasiperiodic Characterisation of a String.
Proceedings of the Prague Stringology Conference 2012, 2012

Efficient Data Structures for the Factor Periodicity Problem.
Proceedings of the String Processing and Information Retrieval, 2012

The Maximum Number of Squares in a Tree.
Proceedings of the Combinatorial Pattern Matching - 23rd Annual Symposium, 2012


  Loading...