License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.20
URN: urn:nbn:de:0030-drops-81888
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8188/
Go to the corresponding LIPIcs Volume Portal

Briët, Jop ; Dvir, Zeev ; Gopi, Sivakanth

Outlaw Distributions and Locally Decodable Codes

pdf-format:
LIPIcs-ITCS-2017-20.pdf (0.6 MB)

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

BibTeX - Entry

@InProceedings{brit_et_al:LIPIcs:2017:8188,
  author =	{Jop Bri{\"e}t and Zeev Dvir and Sivakanth Gopi},
  title =	{{Outlaw Distributions and Locally Decodable Codes}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8188},
  URN =		{urn:nbn:de:0030-drops-81888},
  doi =		{10.4230/LIPIcs.ITCS.2017.20},
  annote =	{Keywords: Locally Decodable Code, VC-dimension, Incidence Geometry, Cayley Hypergraphs}
}

Keywords: Locally Decodable Code, VC-dimension, Incidence Geometry, Cayley Hypergraphs
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI