Buchumschlag

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	De, Rajat, Kempa, Dominik
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
von: De, Rajat, et al.
Veröffentlicht: (2025)

Word Break on SLP-Compressed Texts
von: De, Rajat, et al.
Veröffentlicht: (2025)

Tight Lower Bounds for Central String Queries in Compressed Space
von: Kempa, Dominik, et al.
Veröffentlicht: (2025)

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
von: Kempa, Dominik, et al.
Veröffentlicht: (2023)

Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text
von: Adudodla, Ankith Reddy, et al.
Veröffentlicht: (2025)

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

Engineering Select Support for Hybrid Bitvectors
von: Chiu, Eric, et al.
Veröffentlicht: (2025)

Wavelet Forests Revisited
von: Chiu, Eric, et al.
Veröffentlicht: (2026)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
von: Kempa, Dominik, et al.
Veröffentlicht: (2024)

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

Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees
von: Hu, Ivan, et al.
Veröffentlicht: (2022)

New Algorithms and Lower Bounds for Streaming Tournaments
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

Lower Bounds for Non-adaptive Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

The CDAWG Index and Pattern Matching on Grammar-Compressed Strings
von: Cleary, Alan M., et al.
Veröffentlicht: (2024)

Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings
von: Cleary, Alan M., et al.
Veröffentlicht: (2024)

Dynamic Grammar-Compressed Self-Index in $δ$-Optimal Space
von: Nishimoto, Takaaki, et al.
Veröffentlicht: (2026)

A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
von: Kuszmaul, William
Veröffentlicht: (2025)

Tight Static Lower Bounds for Non-Adaptive Data Structures
von: Persiano, Giuseppe, et al.
Veröffentlicht: (2020)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
von: Hwang, Samuel, et al.
Veröffentlicht: (2024)

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
von: Ghosh, Prantar, et al.
Veröffentlicht: (2024)

LZ78 Substring Compression in Compressed Space
von: Shibata, Hiroki, et al.
Veröffentlicht: (2025)

Substring Compression Variations and LZ78-Derivates
von: Köppl, Dominik
Veröffentlicht: (2024)

Suffixient Arrays: a New Efficient Suffix Array Compression Technique
von: Cenzato, Davide, et al.
Veröffentlicht: (2024)

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

A Lower Bound for Light Spanners in General Graphs
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
von: Yoshida, Yuichi
Veröffentlicht: (2026)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Lower Bounds on $0$-Extension with Steiner Nodes
von: Chen, Yu, et al.
Veröffentlicht: (2024)

Double Exponential Lower Bound for Telephone Broadcast
von: Tale, Prafullkumar
Veröffentlicht: (2024)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
von: Chen, Yu, et al.
Veröffentlicht: (2026)

Dynamic PageRank: Algorithms and Lower Bounds
von: Jayaram, Rajesh, et al.
Veröffentlicht: (2024)

Fine Grained Lower Bounds for Multidimensional Knapsack
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2024)

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

Lower Bounds for Convexity Testing
von: Chen, Xi, et al.
Veröffentlicht: (2024)

A Tight Lower Bound for Cycle Detection in Grid Graphs
von: Au, Andrew
Veröffentlicht: (2026)

Improved Lower Bounds for Privacy under Continual Release
von: Aryanfard, Bardiya, et al.
Veröffentlicht: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
von: Fleming, Noah, et al.
Veröffentlicht: (2026)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
von: Huiberts, Sophie, et al.
Veröffentlicht: (2022)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
von: Funke, Daniel, et al.
Veröffentlicht: (2024)

Lower Bounds on Tree Covers
von: Chen, Yu, et al.
Veröffentlicht: (2025)