An r-query Locally Decodable Code (LDC) encodes k-bit messages to a n(k)-bit codewords, in such a way that every message bit can be recovered with a high probability, by a randomized decoding procedure that reads only r codeword bits, even if the codeword is corrupted in up to delta fraction of locations. Ideally, one would like both the codeword length n and the query complexity r to be as small as possible. One however cannot minimize these parameters simultaneously. There is a trade-off. In the talk I’ll review the recent progress in understanding the true shape of this trade-off.


Based on joint papers with Swastik Kopparty and Shubhangi Saraf, with Zeev Dvir and Parikshit Gopalan, and with Shubhangi Saraf.