Locally decodable codes (LDCs) are error correcting codes with the extra property that it is possible to recover any symbol of a message by reading just a small number of positions of the codeword, and get the correct answer with high probability even if the codeword is corrupted.

We present several bounds on the largest possible correctness for decoding LDCs, as a function of the amount of corruption tolerated and the number of queries used, regardless of the length of the code. Our bounds are close to tight.

We also investigate the relationship between the amount of corruption tolerated by an LDC and its minimum distance as an error correcting code. Even though intuitively the two notions are expected to be related, we demonstrate that in general this is not the case.