{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreid2fbharm4dqdjoksnrykbno2hz5qvgoq6z3a6p7eh27jph4pdjo4",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfnrv7tc6rf2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.20278v1",
  "publishedAt": "2026-02-25T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Alexander R. Block",
    "Jeremiah Blocki",
    "Kuan Cheng",
    "Elena Grigorescu",
    "Xin Li",
    "Yu Zheng",
    "Minshen Zhu"
  ],
  "textContent": "**Authors:** Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu\n\nLocally Decodable Codes (LDCs) are error-correcting codes $C\\colonΣ^n\\rightarrow Σ^m,$ encoding \\emph{messages} in $Σ^n$ to \\emph{codewords} in $Σ^m$, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting. We prove an exponential lower bound on the length of Hamming RLDCs making $2$ queries (even adaptively) over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a ``phase-transition''-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits.",
  "title": "Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes"
}