Imagen de Portada

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	De, Rajat, Kempa, Dominik
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

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
por: De, Rajat, et al.
Publicado: (2023)

Tight Lower Bounds for Central String Queries in Compressed Space
por: Kempa, Dominik, et al.
Publicado: (2025)

Word Break on SLP-Compressed Texts
por: De, Rajat, et al.
Publicado: (2025)

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
por: Kempa, Dominik, et al.
Publicado: (2023)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
por: Kempa, Dominik, et al.
Publicado: (2025)

Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text
por: Adudodla, Ankith Reddy, et al.
Publicado: (2025)

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
por: Duyster, Anouk, et al.
Publicado: (2026)

Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings
por: Cleary, Alan M., 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)

Engineering Select Support for Hybrid Bitvectors
por: Chiu, Eric, et al.
Publicado: (2025)

Wavelet Forests Revisited
por: Chiu, Eric, et al.
Publicado: (2026)

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

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
por: Bodwin, Greg, et al.
Publicado: (2024)

String Indexing with Compressed Patterns
por: Bille, Philip, et al.
Publicado: (2019)

Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
por: Charalampopoulos, Panagiotis, et al.
Publicado: (2026)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
por: Kothari, Pravesh, et al.
Publicado: (2024)

Near-real-time Solutions for Online String Problems
por: Köppl, Dominik, et al.
Publicado: (2026)

Bounding the Optimal Performance of Online Randomized Primal-Dual Methods
por: Xu, Pan
Publicado: (2025)

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

Compressed Dictionary Matching on Run-Length Encoded Strings
por: Bille, Philip, et al.
Publicado: (2025)

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

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

Time-Optimal Construction of String Synchronizing Sets
por: Ellert, Jonas, et al.
Publicado: (2026)

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

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

Near-Optimal Trace Reconstruction for Mildly Separated Strings
por: Aamand, Anders, et al.
Publicado: (2024)

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

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
por: Yoshida, Yuichi
Publicado: (2026)

New Algorithms and Lower Bounds for Streaming Tournaments
por: Ghosh, Prantar, et al.
Publicado: (2024)

Lower Bounds on $0$-Extension with Steiner Nodes
por: Chen, Yu, et al.
Publicado: (2024)

Double Exponential Lower Bound for Telephone Broadcast
por: Tale, Prafullkumar
Publicado: (2024)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
por: Chen, Yu, et al.
Publicado: (2026)

Dynamic PageRank: Algorithms and Lower Bounds
por: Jayaram, Rajesh, et al.
Publicado: (2024)

Fine Grained Lower Bounds for Multidimensional Knapsack
por: Doron-Arad, Ilan, et al.
Publicado: (2024)

LZD-style Compression Scheme with Truncation and Repetitions
por: Götz, Linus, et al.
Publicado: (2025)

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

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

Improved Lower Bounds for Privacy under Continual Release
por: Aryanfard, Bardiya, et al.
Publicado: (2025)

Lower Bounds for Non-adaptive Local Computation Algorithms
por: Azarmehr, Amir, et al.
Publicado: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
por: Fleming, Noah, et al.
Publicado: (2026)