Some New Lower Bounds for General Locally Decodable Codes

David Woodruff
Massachusetts Institute of Technology

I'll first reprove all of the lower bounds for q-query linear locally decodable codes given by Kerenidis and de Wolf, without using any quantum arguments. My proofs are combinatorial and elementary. I'll then show how these new techniques, combined with a deep inequality in quantum information theory, allow me to improve the best known lower bounds for general codes, even non-linear, for any odd q > 1.

This is work in progress.

Audio (MP3 File, Podcast Ready)

Back to Workshop II: Locally decodable codes, private information retrieval, privacy-preserving data-mining, and public key encryption with special properties