Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz–Thompson EstimatorResearch Paper
A stored binary message can be protected by an encoding that expands it into a longer word. A locally decodable code aims to recover one requested message bit after reading only a few coordinates, even when part of the stored word has been corrupted. Its relaxed version permits the decoder to abort on corrupted words. On a valid codeword it must still…