Lower bounds tighten limits on relaxed locally decodable codes
Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator
Computational ComplexityInformation Theory
Summary
This work investigates how efficiently error-correcting codes can allow quick data retrieval even when some data is damaged. The authors show that to maintain these fast checks, the overall code length must grow at least a certain amount, nearly matching previously known upper limits. They handle more general code types with adaptive methods, improving our understanding of the trade-offs involved. Their approach uses a new mathematical tool called the capped Horvitz–Thompson estimator to analyze these decoding methods.
What this means in practice
- •For data storage engineers: Sets fundamental limits on how compactly error-corrected data can support quick, adaptive bit retrieval under errors.
- •For security system developers: Guides design choices for codes enabling verification of data integrity with minimum query effort despite noise.
A theory result. No direct application yet.
Authors
Guy Goldberg, Tom Gur, Sidhant Saraogi
Abstract
We prove a nearly optimal lower bound on the blocklength of general relaxed locally decodable codes (RLDCs), extending the result of [GGS26] to nonlinear encodings and adaptive decoders with two-sided error. Namely, we show that any $q$-query RLDC $C\colon \{0,1\}^k \to \{0,1\}^n$ must satisfy $n = k^{1+Ω(1/q)}$, closely matching the upper bound of $n = k^{1+O(1/q)}$ by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004). Our proof reduces showing RLDC lower bounds to estimating the output distribution of adaptive decoders. To this end, we introduce a capped Horvitz--Thompson estimator with uniformly bounded discrete derivatives on the $p$-biased cube. We establish its concentration of measure via self-bounding inequalities and control the downward bias induced by capping through a spreadness argument.