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.APPROX-RANDOM.2017.30
URN: urn:nbn:de:0030-drops-75792
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7579/
Go to the corresponding LIPIcs Volume Portal

Bhattacharyya, Arnab ; Gopi, Sivakanth ; Tal, Avishay

Lower Bounds for 2-Query LCCs over Large Alphabet

pdf-format:
LIPIcs-APPROX-RANDOM-2017-30.pdf (0.6 MB)

Abstract

A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates. We show that any 2-query locally correctable code C:{0,1}^k -> Sigma^n that can correct a constant fraction of corrupted symbols must have n >= exp(k/\log|Sigma|) under the assumption that the LCC is zero-error. We say that an LCC is zero-error if there exists a non-adaptive corrector algorithm that succeeds with probability 1 when the input is an uncorrupted codeword. All known constructions of LCCs are zero-error.

Our result is tight upto constant factors in the exponent. The only previous lower bound on the length of 2-query LCCs over large alphabet was Omega((k/log|\Sigma|)^2) due to Katz and Trevisan (STOC 2000). Our bound implies that zero-error LCCs cannot yield 2-server private information retrieval (PIR) schemes with sub-polynomial communication. Since there exists a 2-server PIR scheme with sub-polynomial communication (STOC 2015) based on a zero-error 2-query locally decodable code (LDC), we also obtain a separation between LDCs and LCCs over large alphabet.

BibTeX - Entry

@InProceedings{bhattacharyya_et_al:LIPIcs:2017:7579,
  author =	{Arnab Bhattacharyya and Sivakanth Gopi and Avishay Tal},
  title =	{{Lower Bounds for 2-Query LCCs over Large Alphabet}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{30:1--30:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7579},
  URN =		{urn:nbn:de:0030-drops-75792},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.30},
  annote =	{Keywords: Locally correctable code, Private information retrieval, Szemer{\'e}di regularity lemma}
}

Keywords: Locally correctable code, Private information retrieval, Szemerédi regularity lemma
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Issue Date: 2017
Date of publication: 11.08.2017

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