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)
Copyright. All Rights Reserved.