摘要：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∞ 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.
