Skip to main content

Outlaw Distributions and Locally Decodable Codes

Author(s): Briët, Jop; Dvir, Zeev; Gopi, Sivakanth

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBriët, Jop-
dc.contributor.authorDvir, Zeev-
dc.contributor.authorGopi, Sivakanth-
dc.identifier.citationBriët, Jop, Zeev Dvir, and Sivakanth Gopi. "Outlaw Distributions and Locally Decodable Codes." Theory of Computing 15, no. 12 (2019): pp. 1-24. doi:10.4086/toc.2019.v015a012en_US
dc.description.abstractLocally 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. 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.en_US
dc.format.extent1 - 24en_US
dc.relation.ispartofTheory of Computingen_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleOutlaw Distributions and Locally Decodable Codesen_US
dc.typeJournal Articleen_US

Files in This Item:
File Description SizeFormat 
OutlawDistributionLocallyDecodableCodesTheoryComputing.pdf318.74 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.