Skip to content
DraconiticResearch
Search Sources API
197,788 studies31 sourcesUpdated 7 min ago
PreprintCC BY 4.0arXiv

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

  • Guy Goldberg
  • Tom Gur
  • Sidhant Saraogi
Open at sourcePDFDOICite

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: {0,1}k → {0,1}n 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.

Related

  1. Amortized Relaxed Locally Decodable Codes
    Jeremiah Blocki, Justin Zhang
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  2. Upper Bounds for CSP Non-redundancy via Locally Decodable Codes
    Joshua Brakensiek, David Conlon, Venkatesan Guruswami +4
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Adaptive relaxed CQ algorithm with dynamic stepsizes for the split feasibility problem
    Qiao-Li Dong
    arXivPreprintCC BY-NC-ND 4.0Full textOptimisation & controlarXiv
  4. Adaptive Model-Switch Thermodynamic Integration: A Bayes Factor Estimator
    Amanda Malnati, Megan Kralj, Ken D. Olum
    arXivPreprintarXiv licenceFull textHigh-energy astrophysicsStatisticsarXiv
  5. Characterizing Estimator-Regime Transitions in Adaptive Enrichment Trials
    Xin Luo, Maria Kudela, Margaret Gamalo
    arXivPreprintCC BY-NC-ND 4.0Full textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{goldberg2026lower,
  title = {{Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator}},
  author = {Guy Goldberg and Tom Gur and Sidhant Saraogi},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.04678},
  eprint = {2611.04678},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.04678},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator
AU  - Guy Goldberg
AU  - Tom Gur
AU  - Sidhant Saraogi
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.04678
UR  - https://arxiv.org/abs/2611.04678
AB  - 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}^k → {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.
ER  -