Cover Image

Tight Additive Sensitivity on LZ-style Compressors and String Attractors

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fujie, Yuto, Shibata, Hiroki, Nakashima, Yuto, Inenaga, Shunsuke
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

LZBE: an LZ-style compressor supporting $O(\log n)$-time random access
by: Shibata, Hiroki, et al.
Published: (2025)

Sensitivity of Repetitiveness Measures to String Reversal
by: Bannai, Hideo, et al.
Published: (2026)

Tight bounds for the sensitivity of CDAWGs with left-end edits
by: Fujimaru, Hiroto, et al.
Published: (2023)

Analyzing and Leveraging the $k$-Sensitivity of LZ77
by: Bathie, Gabriel, et al.
Published: (2026)

Counting distinct (non-)crossing substrings
by: Umezaki, Haruki, et al.
Published: (2025)

Subsequence Matching and LCS under Cartesian-Tree Equivalence
by: Tsujimoto, Taketo, et al.
Published: (2024)

Edit and Alphabet-Ordering Sensitivity of Lex-parse
by: Nakashima, Yuto, et al.
Published: (2024)

On the Number of Non-equivalent Parameterized Squares in a String
by: Hamai, Rikuya, et al.
Published: (2024)

Faster Space-Efficient STR-IC-LCS Computation
by: Yonemoto, Yuki, et al.
Published: (2022)

Finding Diverse Strings and Longest Common Subsequences in a Graph
by: Shida, Yuto, et al.
Published: (2024)

Online Computation of Palindromes and Suffix Trees on Tries
by: Shibata, Hiroki, et al.
Published: (2026)

Faster and Simpler Online Computation of String Net Frequency
by: Inenaga, Shunsuke
Published: (2024)

Packed Acyclic Deterministic Finite Automata
by: Shibata, Hiroki, et al.
Published: (2024)

Recognizing 2-Layer and Outer $k$-Planar Graphs
by: Kobayashi, Yasuaki, et al.
Published: (2024)

Computing maximal palindromes in non-standard matching models
by: Mieno, Takuya, et al.
Published: (2022)

Nyldon Factorization of Thue-Morse Words and Fibonacci Words
by: Kishi, Kaisei, et al.
Published: (2025)

LZ78 Substring Compression in Compressed Space
by: Shibata, Hiroki, et al.
Published: (2025)

Space-Efficient Online Computation of String Net Occurrences
by: Mieno, Takuya, et al.
Published: (2024)

All-Pairs Suffix-Prefix on Fully Dynamic Set of Strings
by: Kikuchi, Masaru, et al.
Published: (2024)

String Consensus Problems with Swaps and Substitutions
by: Gabory, Estéban, et al.
Published: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Hardness Results on Characteristics for Elastic-Degenerated Strings
by: Köppl, Dominik, et al.
Published: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
by: Grossman, Ofer, et al.
Published: (2023)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
by: Jansen, Klaus, et al.
Published: (2025)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
by: Tate, Elise, et al.
Published: (2025)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
by: Yoshida, Yuichi, et al.
Published: (2025)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Kisfaludi-Bak, Sándor, et al.
Published: (2020)

Tight Inapproximability of Target Set Reconfiguration
by: Ohsaka, Naoto
Published: (2024)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
by: Blanc, Guy, et al.
Published: (2024)

Quantum Algorithm for Lexicographically Minimal String Rotation
by: Wang, Qisheng, et al.
Published: (2020)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
by: Gu, Yuzhou, et al.
Published: (2025)

The CDAWG Index and Pattern Matching on Grammar-Compressed Strings
by: Cleary, Alan M., et al.
Published: (2024)

Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings
by: Cleary, Alan M., et al.
Published: (2024)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
by: Chakraborty, Dipayan, et al.
Published: (2024)