Outlaw Distributions and Locally Decodable Codes

Locally decodable codes (LDCs) are error correcting codes that allow for decoding of a single message bit using a small number of queries to a corrupted encoding. In this work, we give a new characterization of LDCs using distributions over smooth Boolean functions whose expectation is hard to approximate (in~$L_\infty$~norm) with a small number of samples. We give several candidates for such distributions  coming from finite field incidence geometry and from hypergraph (non)expanders. We also prove a useful lemma showing that (smooth) LDCs which are only required to work on average over a random message and a random message index can be turned into true LDCs at the cost of only constant factors in the parameters.