2026-07-22T01:28:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7579 2024-03-06T10:40:39Z ddc:004 open_access

Lower Bounds for 2-Query LCCs over Large Alphabet Bhattacharyya, Arnab Gopi, Sivakanth Tal, Avishay Locally correctable code Private information retrieval Szemerédi regularity lemma 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arnab Bhattacharyya and Sivakanth Gopi and Avishay Tal 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.30 urn:nbn:de:0030-drops-75792 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.30 eng https://creativecommons.org/licenses/by/3.0/legalcode