Outlaw distributions and locally decodablecodes

Jop Briët, Zeev Dvir, Sivakanth Gopi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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 L1 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 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.

Original languageEnglish (US)
Title of host publication8th Innovations in Theoretical Computer Science Conference, ITCS 2017
EditorsChristos H. Papadimitriou
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770293
DOIs
StatePublished - Nov 1 2017
Event8th Innovations in Theoretical Computer Science Conference, ITCS 2017 - Berkeley, United States
Duration: Jan 9 2017Jan 11 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume67
ISSN (Print)1868-8969

Other

Other8th Innovations in Theoretical Computer Science Conference, ITCS 2017
CountryUnited States
CityBerkeley
Period1/9/171/11/17

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Cayley Hypergraphs
  • Incidence Geometry
  • Locally Decodable Code
  • VC-dimension

Fingerprint Dive into the research topics of 'Outlaw distributions and locally decodablecodes'. Together they form a unique fingerprint.

Cite this