Buchumschlag

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Block, Alexander R., Blocki, Jeremiah, Cheng, Kuan, Grigorescu, Elena, Li, Xin, Zheng, Yu, Zhu, Minshen
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Information Theory Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
von: Blocki, Jeremiah, et al.
Veröffentlicht: (2021)

Amortized Locally Decodable Codes
von: Blocki, Jeremiah, et al.
Veröffentlicht: (2025)

Amortized Locally Decodable Codes for Insertions and Deletions
von: Blocki, Jeremiah, et al.
Veröffentlicht: (2025)

A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
von: Janzer, Oliver, et al.
Veröffentlicht: (2024)

When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
von: Cheng, Kuan, et al.
Veröffentlicht: (2026)

On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
von: Cheng, Kuan, et al.
Veröffentlicht: (2023)

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
von: Grigorescu, Elena, et al.
Veröffentlicht: (2025)

PAC codes with Bounded-Complexity Sequential Decoding: Pareto Distribution and Code Design
von: Moradi, Mohsen, et al.
Veröffentlicht: (2024)

Relaxed Local Correctability from Local Testing
von: Kumar, Vinayak M., et al.
Veröffentlicht: (2023)

Decoding Balanced Linear Codes With Preprocessing
von: Bogdanov, Andrej, et al.
Veröffentlicht: (2025)

Advances in List Decoding of Polynomial Codes
von: Kumar, Mrinal, et al.
Veröffentlicht: (2026)

Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
von: Goldberg, Guy, et al.
Veröffentlicht: (2025)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
von: Alrabiah, Omar, et al.
Veröffentlicht: (2024)

Explicit Codes approaching Generalized Singleton Bound using Expanders
von: Jeronimo, Fernando Granha, et al.
Veröffentlicht: (2025)

LDPC Codes Achieve List Decoding Capacity
von: Mosheiff, Jonathan, et al.
Veröffentlicht: (2019)

When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?
von: Doron, Dean, et al.
Veröffentlicht: (2024)

Undirected Multicast Network Coding Gaps via Locally Decodable Codes
von: Braverman, Mark, et al.
Veröffentlicht: (2025)

Improved Decoding of Tanner Codes
von: Zhou, Zhaienhe, et al.
Veröffentlicht: (2025)

Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
von: First, Uriya A., et al.
Veröffentlicht: (2024)

Lower Bounds for Learning Quantum States with Single-Copy Measurements
von: Lowe, Angus, et al.
Veröffentlicht: (2022)

Oblivious Deletion Codes
von: Con, Roni, et al.
Veröffentlicht: (2025)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
von: Basu, Arpon, et al.
Veröffentlicht: (2024)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
von: Srivastava, Shashank, et al.
Veröffentlicht: (2025)

Exponential speedups in fault-tolerant processing of quantum experiments
von: Kannan, Ishaan, et al.
Veröffentlicht: (2026)

Explicit Constant-Alphabet Subspace Design Codes
von: Goyal, Rohan, et al.
Veröffentlicht: (2026)

High Rate Multivariate Polynomial Evaluation Codes
von: Kopparty, Swastik, et al.
Veröffentlicht: (2024)

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
von: Ko, Young Kun
Veröffentlicht: (2026)

The Optimization of Random Tree Codes for Limited Computational Resources
von: Bacinoglu, B. Tan
Veröffentlicht: (2025)

Improved List Size for Folded Reed-Solomon Codes
von: Srivastava, Shashank
Veröffentlicht: (2024)

Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance
von: Fawzi, Omar, et al.
Veröffentlicht: (2023)

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
von: Goyal, Rohan, et al.
Veröffentlicht: (2025)

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes
von: Drucker, Andrew, et al.
Veröffentlicht: (2024)

Punctured Low-Bias Codes Behave Like Random Linear Codes
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2021)

Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs
von: Jeronimo, Fernando Granha, et al.
Veröffentlicht: (2026)

Differentially Private Compression and the Sensitivity of LZ77
von: Blocki, Jeremiah, et al.
Veröffentlicht: (2025)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
von: Gu, Yuzhou, et al.
Veröffentlicht: (2025)

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
von: Gupta, Rishav, et al.
Veröffentlicht: (2026)

Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation
von: Wang, Qisheng
Veröffentlicht: (2025)

An exposition of recent list-size bounds of FRS Codes
von: Garg, Abhibhav, et al.
Veröffentlicht: (2025)

Generic Reed-Solomon Codes Achieve List-decoding Capacity
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2022)