A Lower Bound for Relaxed Locally Decodable Codes

Tom Gur, Oded Lachish

A locally decodable code (LDC) C:{0,1}^k -> {0,1}^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codew…