Tomasz Kociumaka

ACM Trans. Algorithms, July, 2024

Near-Optimal Search Time in δ-Optimal Space, and Vice Versa.

[BibT_eX]

[DOI]

Francisco Olivares

Algorithmica, April, 2024

Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences.

[BibT_eX]

[DOI]

Algorithmica, March, 2024

Internal Pattern Matching Queries in a Text and Applications.

[BibT_eX]

[DOI]

SIAM J. Comput., 2024

Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching.

[BibT_eX]

[DOI]

Jakob Nogler

CoRR, 2024

On the Complexity of Computing the Co-lexicographic Width of a Regular Language.

[BibT_eX]

[DOI]

CoRR, 2024

Lempel-Ziv (LZ77) Factorization in Sublinear Time.

[BibT_eX]

[DOI]

CoRR, 2024

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications.

[BibT_eX]

[DOI]

Egor Gorbachev

CoRR, 2024

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights.

[BibT_eX]

[DOI]

Egor Gorbachev

CoRR, 2024

On the Communication Complexity of Approximate Pattern Matching.

[BibT_eX]

[DOI]

Jakob Nogler

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts.

[BibT_eX]

[DOI]

Anouk Duyster

Proceedings of the String Processing and Information Retrieval, 2024

Brief Announcement: Upper and Lower Bounds for Edit Distance in Space-Efficient MPC.

[BibT_eX]

[DOI]

Jacob Gilbert

MohammadTaghi Hajiaghayi

Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures, 2024

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

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Dynamic Dynamic Time Warping.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Faster Sublinear-Time Edit Distance.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Publisher Correction: Longest Common Substring with Approximately k Mismatches.

[BibT_eX]

[DOI]

Algorithmica, October, 2023

Toward a Definitive Compressibility Measure for Repetitive Sequences.

[BibT_eX]

[DOI]

Nicola Prezza

IEEE Trans. Inf. Theory, April, 2023

Tight Bound for the Number of Distinct Palindromes in a Tree.

[BibT_eX]

[DOI]

Electron. J. Comb., 2023

Weighted Edit Distance Computation: Strings, Trees, and Dyck.

[BibT_eX]

[DOI]

Jacob Gilbert

MohammadTaghi Hajiaghayi

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Breaking the 𝒪(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares.

[BibT_eX]

[DOI]

Gabriel Bathie

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

An Algorithmic Bridge Between Hamming and Levenshtein Distances.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Approximating Edit Distance in the Fully Dynamic Model.

[BibT_eX]

[DOI]

Anish Mukherjee

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.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Optimal Algorithms for Bounded Weighted Edit Distance.

[BibT_eX]

[DOI]

Alejandro Cassis

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths.

[BibT_eX]

[DOI]

Adam Polak

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String.

[BibT_eX]

[DOI]

Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching, 2023

2022

A periodicity lemma for partial words.

[BibT_eX]

[DOI]

Inf. Comput., 2022

Efficient representation and counting of antipower factors in words.

[BibT_eX]

[DOI]

Inf. Comput., 2022

Faster Pattern Matching under Edit Distance.

[BibT_eX]

[DOI]

CoRR, 2022

Resolution of the burrows-wheeler transform conjecture.

[BibT_eX]

[DOI]

Commun. ACM, 2022

Efficient Computation of Sequence Mappability.

[BibT_eX]

[DOI]

Algorithmica, 2022

Dynamic suffix array with polylogarithmic queries and updates.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

An Improved Algorithm for The k-Dyck Edit Distance Problem.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Near-Optimal Search Time in δ-Optimal Space.

[BibT_eX]

[DOI]

Francisco Olivares

Proceedings of the LATIN 2022: Theoretical Informatics, 2022

Computing Longest (Common) Lyndon Subsequences.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 33rd International Workshop, 2022

Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance.

[BibT_eX]

[DOI]

Jacob Gilbert

MohammadTaghi Hajiaghayi

Hamed Saleh

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Approximate Circular Pattern Matching.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

The Dynamic k-Mismatch Problem.

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching, 2022

2021

Maximal unbordered factors of random strings.

[BibT_eX]

[DOI]

Patrick Hagge Cording

Travis Gagie

Mathias Bæk Tejs Knudsen

Theor. Comput. Sci., 2021

Optimal-Time Dictionary-Compressed Indexes.

[BibT_eX]

[DOI]

Anders Roy Christiansen

Mikko Berggren Ettienne

Nicola Prezza

ACM Trans. Algorithms, 2021

Circular pattern matching with k mismatches.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2021

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

[BibT_eX]

[DOI]

CoRR, 2021

Internal Dictionary Matching.

[BibT_eX]

[DOI]

Algorithmica, 2021

Improved dynamic algorithms for longest increasing subsequence.

[BibT_eX]

[DOI]

Saeed Seddighin

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Small-space and streaming pattern matching with $k$ edits.

[BibT_eX]

[DOI]

Ely Porat

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Faster Algorithms for Longest Common Substring.

[BibT_eX]

[DOI]

Solon P. Pissis

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

Universal reconstruction of a string.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

A Linear-Time Algorithm for Seeds Computation.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

String periods in the order-preserving model.

[BibT_eX]

[DOI]

Inf. Comput., 2020

Indexing weighted sequences: Neat and efficient.

[BibT_eX]

[DOI]

Inf. Comput., 2020

Approximating text-to-pattern Hamming distances.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Efficient Enumeration of Distinct Factors Using Package Representations.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2020

Towards a Definitive Measure of Repetitiveness.

[BibT_eX]

[DOI]

Nicola Prezza

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Faster Approximate Pattern Matching: A Unified Approach.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Practical Performance of Space Efficient Data Structures for Longest Common Extensions.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Time-Space Tradeoffs for Finding a Long Common Substring.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

Approximating Longest Common Substring with k mismatches: Theory and Practice.

[BibT_eX]

[DOI]

Garance Gourdel

Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

Dynamic String Alignment.

[BibT_eX]

[DOI]

Shay Mozes

Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

Counting Distinct Patterns in Internal Dictionary Matching.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

Improved Circular k-Mismatch Sketches.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

2019

Pattern Matching and Consensus Problems on Weighted Sequences and Profiles.

[BibT_eX]

[DOI]

Solon P. Pissis

Theory Comput. Syst., 2019

Efficient enumeration of non-equivalent squares in partial words with few holes.

[BibT_eX]

[DOI]

J. Comb. Optim., 2019

Correction to: Longest Common Substring with Approximately k Mismatches.

[BibT_eX]

[DOI]

Algorithmica, 2019

Longest Common Substring with Approximately k Mismatches.

[BibT_eX]

[DOI]

Algorithmica, 2019

Deleting Vertices to Graphs of Bounded Genus.

[BibT_eX]

[DOI]

Marcin Pilipczuk

Algorithmica, 2019

Linear Search by a Pair of Distinct-Speed Robots.

[BibT_eX]

[DOI]

Algorithmica, 2019

Dynamic Dictionary Matching in the Online Model.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

On Longest Common Property Preserved Substring Queries.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2019

Weighted Shortest Common Supersequence Problem Revisited.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2019

The streaming k-mismatch problem.

[BibT_eX]

[DOI]

Raphaël Clifford

Ely Porat

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

RLE Edit Distance in Near Optimal Time.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Circular Pattern Matching with k Mismatches.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 22nd International Symposium, 2019

Quasi-Linear-Time Algorithm for Longest Common Circular Factor.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, 2019

2018

Efficient algorithms for shortest partial seeds in words.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

On the string consensus problem and the Manhattan sequence consensus problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

On Abelian Longest Common Factor with and without RLE.

[BibT_eX]

[DOI]

Szymon Grabowski

Fundam. Informaticae, 2018

Faster Recovery of Approximate Periods over Edit Distance.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2018

Efficient Computation of Sequence Mappability.

[BibT_eX]

[DOI]

Mai Alzamel

Proceedings of the String Processing and Information Retrieval, 2018

Optimal Dynamic Strings.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Longest Unbordered Factor in Quasilinear Time.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

How Much Different Are Two Words with Different Shortest Periods.

[BibT_eX]

[DOI]

Proceedings of the Artificial Intelligence Applications and Innovations, 2018

Edit Distance with Block Operations.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Linear-Time Algorithm for Long LCF with k Mismatches.

[BibT_eX]

[DOI]

Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

2017

Hardness of Approximation for Strip Packing.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2017

Covering problems for partial words and for indeterminate strings.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Fast algorithms for Abelian periods in words and greatest common divisor queries.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

String Powers in Trees.

[BibT_eX]

[DOI]

Algorithmica, 2017

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

[BibT_eX]

[DOI]

Algorithmica, 2017

On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2017

Sparse Suffix Tree Construction in Optimal Time and Space.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Fast computation of abelian runs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Order-preserving indexing.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Computing minimal and maximal suffixes of a substring.

[BibT_eX]

[DOI]

Ignat I. Kolesnichenko

Theor. Comput. Sci., 2016

Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2016

A Fast Branching Algorithm for Cluster Vertex Deletion.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2016

On the greedy algorithm for the Shortest Common Superstring problem with reversals.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2016

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

[BibT_eX]

[DOI]

Solon P. Pissis

CoRR, 2016

Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2016

Minimal Suffix and Rotation of a Substring in Optimal Time.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

Faster Longest Common Extension Queries in Strings over General Alphabets.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

Efficient Index for Weighted Sequences.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

2015

Linear-time version of Holub's algorithm for morphic imprimitivity testing.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

A note on the longest common compatible prefix problem for partial words.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2015

An LP-rounding 2√2-approximation for restricted maximum acyclic subgraph.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Michal Wlodarczyk

Inf. Process. Lett., 2015

Fast Algorithm for Partial Covers in Words.

[BibT_eX]

[DOI]

Algorithmica, 2015

Efficient Algorithms for Longest Closed Factor Array.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2015

Wavelet Trees Meet Suffix Trees.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Subquadratic-Time Algorithms for Abelian Stringology Problems.

[BibT_eX]

[DOI]

Bartlomiej Wisniewski

Proceedings of the Mathematical Aspects of Computer and Information Sciences, 2015

Approximating LZ77 via Small-Space Multiple-Pattern Matching.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

Approximating Upper Degree-Constrained Partial Orientations.

[BibT_eX]

[DOI]

Marek Cygan

Proceedings of the Approximation, 2015

2014

Efficient counting of square substrings in a tree.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

Faster deterministic Feedback Vertex Set.

[BibT_eX]

[DOI]

Marcin Pilipczuk

Inf. Process. Lett., 2014

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

[BibT_eX]

[DOI]

Fabrizio Grandoni

Michal Wlodarczyk

CoRR, 2014

Constant Factor Approximation for Capacitated k-Center with Outliers.

[BibT_eX]

[DOI]

Marek Cygan

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Sublinear Space Algorithms for the Longest Common Substring Problem.

[BibT_eX]

[DOI]

Hjalte Wedel Vildhøj

Proceedings of the Algorithms - ESA 2014, 2014

Computing k-th Lyndon Word and Decoding Lexicographically Minimal de Bruijn Sequence.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

Computing Minimal and Maximal Suffixes of a Substring Revisited.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

2013

Enhanced string covering.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

A note on efficient computation of all Abelian periods in a string.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2013

Order-Preserving Suffix Trees and Their Algorithmic Applications

[BibT_eX]

[DOI]

CoRR, 2013

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

[BibT_eX]

[DOI]

CoRR, 2013

Substring Suffix Selection.

[BibT_eX]

[DOI]