3 papers
cs.DS2026
Analyzing and Leveraging the -Sensitivity of LZ77
Gabriel Bathie, Paul Huber, Guillaume Lagarde +1
We study the sensitivity of the Lempel-Ziv 77 compression algorithm to edits, showing how modifying a string can deteriorate or improve its compression. Our first result is a t…
cs.DS2025
Longest Common Extensions with Wildcards: Trade-off and Applications
Gabriel Bathie, Itai Boneh, Panagiotis Charalampopoulos +2
We study the Longest Common Extension (LCE) problem in a string containing wildcards. Wildcards (also called "don't cares" or "holes") are special characters that match any other c…
cs.DS2025
Small Space Encoding and Recognition of -Palindromic Prefixes
Gabriel Bathie, Jonas Ellert, Tatiana Starikovskaya
Palindromes are non-empty strings that read the same forward and backward. The problem of recognizing strings that can be represented as the concatenation of even-length palindrome…