TR14-025 Authors: Oded Goldreich, Tom Gur, Ilan Komargodski

Publication: 25th February 2014 13:46

Downloads: 3327

Keywords:

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