no. 11 · Monday 9 November 2026
Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz–Thompson Estimator
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.
- fields
- Information Theory