Dominik Kempa

CoRR, September, 2025

Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text.

[BibT_eX]

[DOI]

Ankith Reddy Adudodla

CoRR, June, 2025

On the Hardness Hierarchy for the O(n√log n) Complexity in the Word RAM.

[BibT_eX]

[DOI]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Word Break on SLP-Compressed Texts.

[BibT_eX]

[DOI]

Rajat De

Proceedings of the Data Compression Conference, 2025

2024

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data.

[BibT_eX]

[DOI]

Rajat De

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

Lempel-Ziv (LZ77) Factorization in Sublinear Time.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Breaking the 𝒪(<i>n</i>)-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

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

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

An Upper Bound and Linear-Space Queries on the LZ-End Parsing.

[BibT_eX]

[DOI]

Barna Saha

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

2021

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

[BibT_eX]

[DOI]

CoRR, 2021

Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing.

[BibT_eX]

[DOI]

Ben Langmead

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

2020

Resolution of the Burrows-Wheeler Transform Conjecture.

[BibT_eX]

[DOI]

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

2019

Better External Memory LCP Array Construction.

[BibT_eX]

[DOI]

ACM J. Exp. Algorithmics, 2019

Fixed Block Compression Boosting in FM-Indexes: Theory and Practice.

[BibT_eX]

[DOI]

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

Optimal Construction of Compressed Indexes for Highly Repetitive Texts.

[BibT_eX]

[DOI]

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

2018

Diverse Palindromic Factorization is NP-Complete.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2018

At the roots of dictionary compression: string attractors.

[BibT_eX]

[DOI]

Nicola Prezza

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

String Attractors: Verification and Optimization.

[BibT_eX]

[DOI]

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

Hybrid Indexing Revisited.

[BibT_eX]

[DOI]

Héctor Ferrada

Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments, 2018

2017

Closing in on Time and Space Optimal Construction of Compressed Indexes.

[BibT_eX]

[DOI]

CoRR, 2017

Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet.

[BibT_eX]

[DOI]

Proceedings of the 16th International Symposium on Experimental Algorithms, 2017

On the Size of Lempel-Ziv and Lyndon Factorizations.

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

LZ-End Parsing in Linear Time.

[BibT_eX]

[DOI]

Dmitry Kosolobov

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

LZ-End Parsing in Compressed Space.

[BibT_eX]

[DOI]

Dmitry Kosolobov

Proceedings of the 2017 Data Compression Conference, 2017

Engineering External Memory Induced Suffix Sorting.

[BibT_eX]

[DOI]

Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments, 2017

2016

Lazy Lempel-Ziv Factorization Algorithms.

[BibT_eX]

[DOI]

ACM J. Exp. Algorithmics, 2016

Lempel-Ziv Decoding in External Memory.

[BibT_eX]

[DOI]

Proceedings of the Experimental Algorithms - 15th International Symposium, 2016

LCP Array Construction Using O(sort(n)) (or Less) I/Os.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2016

Faster External Memory LCP Array Construction.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Faster, Minuter.

[BibT_eX]

[DOI]

Proceedings of the 2016 Data Compression Conference, 2016

2015

Efficient Construction of Fundamental Data Structures in Large-Scale Text Indexing.

[BibT_eX]

[DOI]

PhD thesis, 2015

Diverse Palindromic Factorization is NP-Complete.

[BibT_eX]

[DOI]

CoRR, 2015

Diverse Palindromic Factorization Is NP-complete.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 19th International Conference, 2015

Parallel External Memory Suffix Sorting.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

Tighter Bounds for the Sum of Irreducible LCP Values.

[BibT_eX]

[DOI]

Marcin Piatkowski

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

2014

A subquadratic algorithm for minimum palindromic factorization.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2014

LCP Array Construction in External Memory.

[BibT_eX]

[DOI]

Proceedings of the Experimental Algorithms - 13th International Symposium, 2014

Faster Sparse Suffix Sorting.

[BibT_eX]

[DOI]

Tomohiro I

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

Engineering a Lightweight External Memory Suffix Array Construction Algorithm.

[BibT_eX]

[DOI]

Proceedings of the 2nd International Conference on Algorithms for Big Data , 2014

Hybrid Compression of Bitvectors for the FM-Index.

[BibT_eX]

[DOI]

Proceedings of the Data Compression Conference, 2014

Lempel-Ziv Parsing in External Memory.

[BibT_eX]

[DOI]

Proceedings of the Data Compression Conference, 2014

String Range Matching.

[BibT_eX]

[DOI]

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

2013

Lightweight Lempel-Ziv Parsing.

[BibT_eX]

[DOI]

Proceedings of the Experimental Algorithms, 12th International Symposium, 2013

Crochemore's String Matching Algorithm: Simplification, Extensions, Applications.

[BibT_eX]

[DOI]

Proceedings of the Prague Stringology Conference 2013, Prague, Czech Republic, 2013

Linear Time Lempel-Ziv Factorization: Simple, Fast, Small.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

Lempel-Ziv factorization: Simple, fast, practical.

[BibT_eX]

[DOI]

Proceedings of the 15th Meeting on Algorithm Engineering and Experiments, 2013

2012

Grammar Precompression Speeds Up Burrows-Wheeler Compression.

[BibT_eX]

[DOI]

Pekka Mikkola

Proceedings of the String Processing and Information Retrieval, 2012

Slashing the Time for BWT Inversion.

[BibT_eX]

[DOI]