Goldreich, Oded ;
Gur, Tom ;
Komargodski, Ilan
Strong Locally Testable Codes with Relaxed Local Decoders
Abstract
Locally testable codes (LTCs) are errorcorrecting codes that admit very efficient codeword tests. An LTC is said to be strong if it has a proximityoblivious tester; that is, a tester that makes only a constant number of queries and reject noncodewords with probability that depends solely on their distance from the code. Locally decodable codes (LDCs) are complimentary to LTCs. While the latter allow for highly efficient rejection of strings that are far from being codewords, LDCs allow for highly efficient recovery of individual bits of the information that is encoded in strings that are close to being codewords.
While there are known constructions of strongLTCs with nearlylinear length, the existence of a constantquery LDC with polynomial length is a major open problem. In an attempt to bypass this barrier, BenSasson et al. (SICOMP 2006) introduced a natural relaxation of local decodability, called relaxedLDCs. This notion requires local recovery of nearly all individual informationbits, yet allows for recoveryfailure (but not error) on the rest. BenSasson et al. constructed a constantquery relaxedLDC with nearlylinear length (i.e., length k^(1 + alpha) for an arbitrarily small constant alpha>0, where k is the dimension of the code).
This work focuses on obtaining strong testability and relaxed decodability simultaneously. We construct a family of binary linear codes of nearlylinear length that are both strongLTCs (with onesided error) and constantquery relaxedLDCs. This improves upon the previously known constructions, which obtain either weak LTCs or require polynomial length.
Our construction heavily relies on tensor codes and PCPs. In particular, we provide strong canonical PCPs of proximity for membership in any linear code with constant rate and relative distance. Loosely speaking, these are PCPs of proximity wherein the verifier is proximity oblivious (similarly to strongLTCs and every valid statement has a unique canonical proof. Furthermore, the verifier is required to reject noncanonical proofs (even for valid statements).
As an application, we improve the best known separation result between the complexity of decision and verification in the setting of property testing.
BibTeX  Entry
@InProceedings{goldreich_et_al:LIPIcs:2015:5050,
author = {Oded Goldreich and Tom Gur and Ilan Komargodski},
title = {{Strong Locally Testable Codes with Relaxed Local Decoders}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {141},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5050},
URN = {urn:nbn:de:0030drops50507},
doi = {10.4230/LIPIcs.CCC.2015.1},
annote = {Keywords: Locally Testable Codes, Locally Decodable Codes, PCPs of Proximity}
}
2015
Keywords: 

Locally Testable Codes, Locally Decodable Codes, PCPs of Proximity 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

2015 