Cover Image

When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cheng, Kuan, Li, Xin, Mao, Songtao
Format:	Preprint
Published:	2026
Subjects:	Information Theory Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
by: Gur, Tom, et al.
Published: (2025)

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
by: Block, Alexander R., et al.
Published: (2026)

LDPC Codes Achieve List Decoding Capacity
by: Mosheiff, Jonathan, et al.
Published: (2019)

Random Reed-Solomon Codes are List Recoverable with Optimal List Size
by: Doron, Dean, et al.
Published: (2024)

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

Punctured Low-Bias Codes Behave Like Random Linear Codes
by: Guruswami, Venkatesan, et al.
Published: (2021)

An exposition of recent list-size bounds of FRS Codes
by: Garg, Abhibhav, et al.
Published: (2025)

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

Generic Reed-Solomon Codes Achieve List-decoding Capacity
by: Brakensiek, Joshua, et al.
Published: (2022)

Secret Sharing on Superconcentrator
by: Li, Yuan
Published: (2023)

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
by: Blocki, Jeremiah, et al.
Published: (2021)

Constant Degree Direct Product Testers with Small Soundness
by: Bafna, Mitali, et al.
Published: (2024)

Explicit Good Codes Approaching Distance 1 in Ulam Metric
by: Goldenberg, Elazar, et al.
Published: (2024)

Two-Source and Affine Non-Malleable Extractors for Small Entropy
by: Li, Xin, et al.
Published: (2024)

Relaxed Local Correctability from Local Testing
by: Kumar, Vinayak M., et al.
Published: (2023)

Improved Explicit Near-Optimal Codes in the High-Noise Regimes
by: Li, Xin, et al.
Published: (2024)

Multivariate Analytic Combinatorics for Cost Constrained Channels
by: Lenz, Andreas, et al.
Published: (2021)

The edge of the asymptotic spectrum of tensors
by: Alman, Josh, et al.
Published: (2026)

Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
by: Bhattacharya, Sudatta, et al.
Published: (2025)

When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?
by: Doron, Dean, et al.
Published: (2024)

All Kronecker coefficients are reduced Kronecker coefficients
by: Ikenmeyer, Christian, et al.
Published: (2023)

HNN extensions of free groups with equal associated subgroups of finite index: polynomial time word problem
by: Shen, Hanwen, et al.
Published: (2025)

Quasipolynomial bounds for the corners theorem
by: Jaber, Michael, et al.
Published: (2025)

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
by: Dikstein, Yotam, et al.
Published: (2024)

On the degree of polynomials computing square roots mod p
by: Kedlaya, Kiran, et al.
Published: (2023)

Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
by: Ikenmeyer, Christian, et al.
Published: (2022)

On the Structure of Hamiltonian Graphs with Small Independence Number
by: Jedličková, Nikola, et al.
Published: (2024)

When can an expander code correct $Ω(n)$ errors in $O(n)$ time?
by: Cheng, Kuan, et al.
Published: (2023)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
by: Li, Xin, et al.
Published: (2023)

Improved Small Set Expansion in High Dimensional Expanders
by: Kaufman, Tali, et al.
Published: (2025)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
by: Hsieh, Jun-Ting, et al.
Published: (2024)

Oblivious Deletion Codes
by: Con, Roni, et al.
Published: (2025)

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes
by: Drucker, Andrew, et al.
Published: (2024)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
by: Gaspers, Serge, et al.
Published: (2025)

Decoding Balanced Linear Codes With Preprocessing
by: Bogdanov, Andrej, et al.
Published: (2025)

Quasi-linear time decoding of RS and AG codes for burst errors up to the Singleton bound
by: Li, Songsong, et al.
Published: (2025)

Coboundary expansion of coset complexes
by: Kaufman, Tali, et al.
Published: (2024)

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
by: Panova, Greta
Published: (2025)

Explicit Constant-Alphabet Subspace Design Codes
by: Goyal, Rohan, et al.
Published: (2026)

Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs
by: Jeronimo, Fernando Granha, et al.
Published: (2026)