Imagen de Portada

On the complexity and approximability of Bounded access Lempel Ziv coding

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Cicalese, Ferdinando, Ugazio, Francesca
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Height-bounded Lempel-Ziv encodings
por: Bannai, Hideo, et al.
Publicado: (2024)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
por: Kempa, Dominik, et al.
Publicado: (2024)

Faster and simpler online/sliding rightmost Lempel-Ziv factorizations
por: Sumiyoshi, Wataru, et al.
Publicado: (2024)

Sketching approximations and LP approximations for finite CSPs are related
por: Singer, Noah G., et al.
Publicado: (2025)

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

On approximability of the Permanent of PSD matrices
por: Ebrahimnejad, Farzam, et al.
Publicado: (2024)

Simple approximation algorithms for Polyamorous Scheduling
por: Biktairov, Yuriy, et al.
Publicado: (2024)

Streaming approximation resistance of every ordering CSP
por: Singer, Noah G., et al.
Publicado: (2021)

Lower Bounds for Convexity Testing
por: Chen, Xi, et al.
Publicado: (2024)

Kernelization Bounds for Constrained Coloring
por: Haviv, Ishay
Publicado: (2026)

Clustering with Locally Bounded Ignorance
por: Garvardt, Jaroslav, et al.
Publicado: (2026)

Residue Domination in Bounded-Treewidth Graphs
por: Greilhuber, Jakob, et al.
Publicado: (2024)

Improved Space Bounds for Subset Sum
por: Belova, Tatiana, et al.
Publicado: (2024)

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

The Structure of In-Place Space-Bounded Computation
por: Cook, James, et al.
Publicado: (2025)

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

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

MAX BISECTION might be harder to approximate than MAX CUT
por: Brakensiek, Joshua, et al.
Publicado: (2025)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
por: Singer, Noah G.
Publicado: (2025)

The communication complexity of distributed estimation
por: Gopalan, Parikshit, et al.
Publicado: (2025)

Parameterized complexity of reconfiguration of atoms
por: Cooper, Alexandre, et al.
Publicado: (2021)

Treedepth Inapproximability and Exponential ETH Lower Bound
por: Bonnet, Édouard, et al.
Publicado: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
por: Wang, Yichuan
Publicado: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
por: Chou, Chi-Ning, et al.
Publicado: (2021)

Structural Parameterizations for Two Bounded Degree Problems Revisited
por: Lampis, Michael, et al.
Publicado: (2023)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
por: Li, Qian, et al.
Publicado: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
por: Fei, Yumou, et al.
Publicado: (2026)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
por: Putterman, Aaron, et al.
Publicado: (2026)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
por: Esmer, Barış Can, et al.
Publicado: (2024)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
por: Assadi, Sepehr, et al.
Publicado: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
por: Singer, Noah G., et al.
Publicado: (2026)

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

On girth and the parameterized complexity of token sliding and token jumping
por: Bartier, Valentin, et al.
Publicado: (2020)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
por: Assadi, Sepehr, et al.
Publicado: (2024)

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
por: Ko, Young Kun
Publicado: (2025)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
por: Enright, Jessica, et al.
Publicado: (2020)

The complexity of testing all properties of planar graphs, and the role of isomorphism
por: Basu, Sabyasachi, et al.
Publicado: (2021)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
por: Michel, Lukas, et al.
Publicado: (2023)

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

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