Theory of Computing
-------------------
Title     : Outlaw Distributions and Locally Decodable Codes
Authors   : Jop Briet, Zeev Dvir, and Sivakanth Gopi
Volume    : 15
Number    : 12
Pages     : 1-24
URL       : https://theoryofcomputing.org/articles/v015a012

Abstract
--------

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. Despite decades of study, the optimal trade-
off between query complexity and codeword length is far from
understood. In this work, we give a new characterization of LDCs using
distributions over Boolean functions whose expectation is hard to
approximate (in $L_\infty$ norm) with a small number of samples. We
coin the term "outlaw distributions" for such distributions since they
"defy" the Law of Large Numbers. We show that the existence of outlaw
distributions over sufficiently "smooth" functions implies the
existence of constant query LDCs and vice versa. We give several
candidates for outlaw distributions over smooth functions coming from
finite field incidence geometry, additive combinatorics and 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.

--------------

A conference version of this paper appeared in the Proc. 8th Innovations 
in Theoretical Computer Science Conf. (ITCS 2017).  The present version
includes a new application of the results to a problem from additive
combinatorics (Corollary 1.7) and corrects a minor error in the proof
of Theorem 3.1.