Research Themes
String Algorithms
We design algorithms and data structures — such as suffix arrays and suffix trees — for fast pattern discovery and analysis over massive texts.
- Computing maximal palindromes in non-standard matching models — Inf. Comput., 2025
- Counting Distinct (Non-)crossing Substrings — String Processing and Information Retrieval - 32nd International Symposium, SPIRE 2025, London, UK, September 8-11, 2025, Proceedings
- Text Indexing for Simple Regular Expressions — 36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025, Milan, Italy, June 17-19, 2025
Combinatorics on Words
We analyze the combinatorial structure of repetitions and periodicities in strings, studying measures of repetitiveness and their theoretical limits.
- The "Runs" Theorem — SIAM J. Comput., 2017
- Computing Longest (Common) Lyndon Subsequences — Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings
- Lyndon Arrays in Sublinear Time — 31st Annual European Symposium on Algorithms, ESA 2023, Amsterdam, The Netherlands, September 4-6, 2023
- The Smallest String Attractors of Fibonacci and Period-Doubling Words — 37th Annual Symposium on Combinatorial Pattern Matching, CPM 2026, Copenhagen, Denmark, June 15-17, 2026
Data Compression
We study compression schemes such as the Burrows-Wheeler transform and LZ77, analyzing their theoretical compressiveness and designing algorithms that search and analyze data directly in compressed form.
- On Repetitiveness Measures of Thue-Morse Words — String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings
- Computing NP-Hard Repetitiveness Measures via MAX-SAT — 30th Annual European Symposium on Algorithms, ESA 2022, Berlin/Potsdam, Germany, September 5-9, 2022
- Height-Bounded Lempel-Ziv Encodings — 32nd Annual European Symposium on Algorithms, ESA 2024, Royal Holloway, London, United Kingdom, September 2-4, 2024
- On the Compressiveness of the Burrows-Wheeler Transform — 36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025, Milan, Italy, June 17-19, 2025