文章基本信息

标题：Outlaw Distributions and Locally Decodable Codes
本地全文：下载
作者：Jop Briët ; Zeev Dvir ; Sivakanth Gopi 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2019
卷号：15
页码：1-24
DOI：10.4086/toc.2019.v015a012
出版社：University of Chicago
摘要：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.
关键词：locally decodable codes; Boolean functions; incidence geometry; pseudorandomness;; influence; gaussian width; hypergraphs