The exponential lower bound for 2-query binary Locally Decodable Codes was proved by Kerenidis and de Wolf using difficult quantum information tools. These tools do not seem to be easily adaptable to the case of q-query codes, for q > 2.
It seems reasonable to try and look for a more elementary proof of this result, in the hope that such a proof would be easier to modify to other settings. We will present such an attempt, following the proof of Kerenidis and de Wolf.
We show a simple linear-algebraic reduction of the problem to the setting of Nayak's quantum storage theorem. We then give a proof of Nayak's theorem from 'first principles', using standard tools from linear algebra and convexity. The potential function we use is somewhat different from quantum entropy. This provides additional information, indicating Nayak's theorem to be tight only if the encoding matrices
(essentially) commute.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.