Imagen de Portada

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Boneh, Itai, Golan, Shay, Kraus, Matan
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Deterministic Longest Common Subsequence Approximation in Near-Linear Time
por: Boneh, Itai, et al.
Publicado: (2025)

Hamming Distance Oracle
por: Boneh, Itai, et al.
Publicado: (2024)

Searching 2D-Strings for Matching Frames
por: Boneh, Itai, et al.
Publicado: (2023)

Hairpin Completion Distance Lower Bound
por: Boneh, Itai, et al.
Publicado: (2024)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
por: Boneh, Itai, et al.
Publicado: (2025)

String Problems in the Congested Clique Model
por: Golan, Shay, et al.
Publicado: (2025)

String 2-Covers with No Length Restrictions
por: Boneh, Itai, et al.
Publicado: (2024)

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
por: Boneh, Itai, et al.
Publicado: (2025)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
por: Boneh, Itai, et al.
Publicado: (2025)

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

Balancing Two-Dimensional Straight-Line Programs
por: Boneh, Itai, et al.
Publicado: (2025)

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

Longest Common Extensions with Wildcards: Trade-off and Applications
por: Bathie, Gabriel, et al.
Publicado: (2024)

Fully dynamic biconnectivity in $\tilde{\mathcal{O}}(\log^2 n)$ time
por: Holm, Jacob, et al.
Publicado: (2025)

BAT-LZ Out of Hell
por: Lipták, Zsuzsanna, et al.
Publicado: (2024)

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

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
por: Solomon, Shay, et al.
Publicado: (2023)

The Contiguous Art Gallery Problem is in Θ(n log n)
por: de Berg, Sarita, et al.
Publicado: (2025)

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

Substring Compression Variations and LZ78-Derivates
por: Köppl, Dominik
Publicado: (2024)

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
por: Kenneth-Mordoch, Yotam, et al.
Publicado: (2025)

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths
por: Atalig, Sunny, et al.
Publicado: (2025)

RLZ-r and LZ-End-r: Enhancing Move-r
por: Dinklage, Patrick, et al.
Publicado: (2025)

Computing the LZ-End parsing: Easy to implement and practically efficient
por: Dinklage, Patrick
Publicado: (2024)

Dynamic Set Cover with Worst-Case Recourse
por: Solomon, Shay, et al.
Publicado: (2025)

Improved Time-Space Tradeoffs for 3SUM-Indexing
por: Dinur, Itai, et al.
Publicado: (2025)

Local Routing on Ordered $Θ$-graphs
por: van Renssen, André, et al.
Publicado: (2025)

Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
por: Rao, Satish
Publicado: (2025)

A Lossless Deamortization for Dynamic Greedy Set Cover
por: Solomon, Shay, et al.
Publicado: (2024)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
por: Bukov, Anton, et al.
Publicado: (2023)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
por: Bhattacharya, Sayan, et al.
Publicado: (2024)

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

Distances in Planar Graphs are Almost for Free!
por: Mozes, Shay, et al.
Publicado: (2026)

On the Adversarial Robustness of Online Importance Sampling
por: Kenneth-Mordoch, Yotam, et al.
Publicado: (2025)

Exact (n + 2) Comparison Complexity for the N-Repeated Element Problem
por: Au, Andrew
Publicado: (2026)

Connectivity Labeling in Faulty Colored Graphs
por: Petruschka, Asaf, et al.
Publicado: (2024)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
por: Kempa, Dominik, et al.
Publicado: (2025)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
por: Huang, Shang-En, et al.
Publicado: (2016)

Tree-Like Shortcuttings of Trees
por: Le, Hung, et al.
Publicado: (2025)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
por: Bhattacharya, Sayan, et al.
Publicado: (2024)