New Locally Decodable Codes and Private Information Retrieval Schemes

Abstract A q query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such thatone can probabilistically recover any bit xi of the message by querying only q bits of the codeword C(x), evenafter some constant fraction of codeword bits has been corrupted. We give new constructions of three query LDCs of vastly shorter length than that of previous constructions.Specifically, given any Mersenne prime p = 2t- 1, we design three query LDCs of length N = exp \Gamma n1/t\Delta, for every n. Based on the largest known Mersenne prime, this translates to a length of less than exp in10