Backend
Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
arXiv math.IT0 views
arXiv:2602.20278v3 Announce Type: replace Abstract: Locally Decodable Codes (LDCs) are error-correcting codes $C\colon\Sigma^n\rightarrow \Sigma^m,$ encoding \emph{messages} in $\Sigma^n$ to \emph{codewords} in $\Sigma^m$, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size, while tolerating a constant-fraction of errors. In a very surprising result, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and slightly super-linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we prove an exponential lower bound on the length of Hamming RLDCs making $2$ queries (even adaptively) over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a "phase-transition"-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to LDCs, using a careful analysis of restrictions of message bits that fix codeword bits.
Source:https://arxiv.org/abs/2602.20278PreviousUnique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial ErrorsNextA Block Hierarchy for Rate-Distortion and Dispersion of Binary Markov Sources
Related posts

PostgreSQL 19 removes the MultiXact members wall. Reclamation still waits for template0.
0dev.to
Hugging Face Breach: Security Lessons for AI Agents
0dev.to
Incus Project and Migration Trust Boundaries Need Separate Review
0dev.to

Next.js `revalidatePath` vs `revalidateTag` in 2026: Choosing the Right Cache Invalidation Primitive at Scale
0dev.to

'python' Is Not Recognized as an Internal or External Command: Every Fix
0dev.to

Xcode Instruments in Practice: Profiling and Optimizing iOS Apps
0dev.to