Copertina

Analyzing and Leveraging the $k$-Sensitivity of LZ77

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bathie, Gabriel, Huber, Paul, Lagarde, Guillaume, Zemmari, Akka
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
di: Fujie, Yuto, et al.
Pubblicazione: (2025)

The Trichotomy of Regular Property Testing
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)

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

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
di: Ducoffe, Guillaume
Pubblicazione: (2026)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
di: S., Karthik C., et al.
Pubblicazione: (2024)

k-SUM Hardness Implies Treewidth-SETH
di: Lampis, Michael
Pubblicazione: (2025)

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

A Note on Approximability of Densest At-Least-k-Subgraph
di: Laekhanukit, Bundit, et al.
Pubblicazione: (2026)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
di: Austrin, Per, et al.
Pubblicazione: (2024)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
di: Buhrman, Harry, et al.
Pubblicazione: (2025)

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

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

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
di: Mao, Songtao
Pubblicazione: (2026)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
di: Maalouly, Nicolas El, et al.
Pubblicazione: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
di: Lee, Euiwoong, et al.
Pubblicazione: (2024)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
di: Scheder, Dominik, et al.
Pubblicazione: (2025)

On connections between k-coloring and Euclidean k-means
di: Aman, Enver, et al.
Pubblicazione: (2024)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
di: Mu, Ta-Yu, et al.
Pubblicazione: (2024)

Small Space Encoding and Recognition of $k$-Palindromic Prefixes
di: Bathie, Gabriel, et al.
Pubblicazione: (2024)

Fine-Grained Complexity of Continuous Euclidean k-Center
di: Blank, Lotte, et al.
Pubblicazione: (2026)

Near-Optimal Bounds for Parameterized Euclidean k-means
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2026)

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

On the Hardness of Approximation of the Fair k-Center Problem
di: Thejaswi, Suhas
Pubblicazione: (2026)

Maximum $k$- vs. $\ell$-colourings of graphs
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2023)

$O(n +f(k))$: Truly Linear FPT
di: Bumpus, Benjamin Merlin, et al.
Pubblicazione: (2026)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
di: Hirahara, Shuichi, et al.
Pubblicazione: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
di: Hirahara, Shuichi, et al.
Pubblicazione: (2024)

Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm
di: Goodrich, Michael T., et al.
Pubblicazione: (2024)

The complexity of strong conflict-free vertex-connection $k$-colorability
di: Hsieh, Sun-Yuan, et al.
Pubblicazione: (2024)

Neighborhood-Aware Graph Labeling Problem
di: Shahverdikondori, Mohammad, et al.
Pubblicazione: (2026)

Lazy Kronecker Product
di: Song, Zhao
Pubblicazione: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
di: Nederlof, Jesper
Pubblicazione: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
di: Jiang, Cheng, et al.
Pubblicazione: (2026)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
di: Wang, Chengu
Pubblicazione: (2026)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
di: Asadi, Vahid R., et al.
Pubblicazione: (2026)

NP-Hardness and a PTAS for the Pinwheel Problem
di: Kleinberg, Robert, et al.
Pubblicazione: (2026)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
di: Bodlaender, Hans L., et al.
Pubblicazione: (2026)

Online Orthogonal Vectors Revisited
di: Gajulapalli, Karthik, et al.
Pubblicazione: (2026)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
di: Sharma, Amatya, et al.
Pubblicazione: (2026)