The Library
Strong locally testable codes with relaxed local decoders
Tools
Goldreich, Oded, Gur, Tom and Komargodski , Ilan (2015) Strong locally testable codes with relaxed local decoders. In: 30th Conference on Computational Complexity (CCC’15). Published in: 30th Conference on Computational Complexity (CCC 2015), 33 pp. 1-41. doi:10.4230/LIPIcs.CCC.2015.1
|
PDF
WRAP-strong-locally-testable-codes-relaxed-decorders-Gur-2015.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (825Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.CCC.2015.1
Abstract
Locally testable codes (LTCs) are error-correcting codes that admit very efficient codeword tests. An LTC is said to be strong if it has a proximity-oblivious tester; that is, a tester that makes only a constant number of queries and reject non-codewords 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 strong-LTCs with nearly-linear length, the existence of a constant-query LDC with polynomial length is a major open problem. In an attempt to bypass this barrier, Ben-Sasson et al. (SICOMP 2006) introduced a natural relaxation of local decodability, called relaxed-LDCs. This notion requires local recovery of nearly all individual information-bits, yet allows for recovery-failure (but not error) on the rest. Ben-Sasson et al. constructed a constant-query relaxed-LDC with nearly-linear 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 nearly-linear length that are both strong-LTCs (with one-sided error) and constant-query relaxed-LDCs. 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 strong-LTCs and every valid statement has a unique canonical proof. Furthermore, the verifier is required to reject non-canonical 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.
Item Type: | Conference Item (Paper) | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Computer programming, Error messages (Computer science) | |||||||||||||||
Journal or Publication Title: | 30th Conference on Computational Complexity (CCC 2015) | |||||||||||||||
Publisher: | ACM | |||||||||||||||
Book Title: | Proceeding CCC '15 Proceedings of the 30th Conference on Computational Complexity Pages 1-41 | |||||||||||||||
Official Date: | 2015 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 33 | |||||||||||||||
Page Range: | pp. 1-41 | |||||||||||||||
DOI: | 10.4230/LIPIcs.CCC.2015.1 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
Date of first compliant deposit: | 11 April 2019 | |||||||||||||||
Date of first compliant Open Access: | 11 April 2019 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Conference Paper Type: | Paper | |||||||||||||||
Title of Event: | 30th Conference on Computational Complexity (CCC’15) | |||||||||||||||
Type of Event: | Conference | |||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year