Paper Info
Title
Outlaw distributions and locally decodable codes.
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 u0027outlaw distributionsu0027 for such distributions since they u0027defyu0027 the Law of Large Numbers. We show that the existence of outlaw distributions over sufficiently u0027smoothu0027 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 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.
Year
DOI
Venue
2017
10.4230/LIPIcs.ITCS.2017.20
conference on innovations in theoretical computer science
DocType
Volume
Citations 
Conference
abs/1609.06355
0
PageRank 
References 
Authors
0.34
10
3
Name
Order
Citations
PageRank
Jop Briet1457.41
Zeev Dvir243730.85
Sivakanth Gopi3255.63