Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RLDC:
Reports tagged with RLDC:
TR26-293 | 3rd November 2026
Guy Goldberg, Tom Gur, Sidhant Saraogi

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\colon \{0,1\}^k \to \{0,1\}^n$ must satisfy $n = k^{1+\Omega(1/q)}$, closely matching the ... more >>>




ISSN 1433-8092 | Imprint