Tight Additive Sensitivity on LZ-style Compressors and String Attractors

The worst-case additive sensitivity of a string repetitiveness measure $c$ is defined to be the largest difference between $c(w)$ and $c(w')$, where $w$ is a string of length $n$ and $w'$ is a string that can be obtained by performing a single-character edit operation on $w$. We present $O(\sqrt{n})$ upper bounds for the worst-case additive sensitivity of the smallest string attractor size $γ$ and the smallest bidirectional scheme size $b$, which match the known lower bounds $Ω(\sqrt{n})$ for $γ$ and $b$ [Akagi et al. 2023]. Further, we present matching upper and lower bounds for the worst-case additive sensitivity of the Lempel-Ziv family - $Θ(n^{\frac{2}{3}})$ for LZSS and LZ-End, and $Θ(n)$ for LZ78.