Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator

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 \0,1\ᵏ → \0,1\ⁿ must satisfy n = k1+Ω(1/q), closely matching the upper bound of n = k1+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.