TR16-122 Authors: Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf

Publication: 11th August 2016 08:51

Downloads: 1921

Keywords:

One of the most important open problems in the theory

of error-correcting codes is to determine the

tradeoff between the rate $R$ and minimum distance $\delta$ of a binary

code. The best known tradeoff is the Gilbert-Varshamov bound,

and says that for every $\delta \in (0, 1/2)$, there are codes

with minimum distance $\delta$ and rate $R = R_{GV}(\delta) > 0$ (for

a certain simple function $R_{GV}(\cdot)$). In this paper

we show that the Gilbert-Varshamov bound can be achieved

by codes which support local error-detection and

error-correction algorithms.

Specifically, we show the following results.

1. Local Testing: For all $\delta \in (0,1/2)$ and all $R < R_{GV}(\delta)$,

there exist codes with length $n$, rate $R$ and minimum distance $\delta$

that are locally testable with $quasipolylog(n)$

query complexity.

2. Local Correction: For all positive $\epsilon$, for all $\delta < 1/2$ sufficiently

large, and all $R < (1-\epsilon) R_{GV}(\delta)$, there exist codes with length $n$,

rate $R$ and minimum distance $\delta$ that are locally correctable

from $\frac{\delta}{2} - o(1)$ fraction errors with $O(n^{\epsilon})$ query complexity.

Furthermore, these codes have an efficient randomized construction,

and the local testing and local correction algorithms can

be made to run in time polynomial in the query complexity.

Our results on locally correctable codes also immediately give locally decodable codes with the same parameters.

Our local testing result is obtained by combining Thommesen's random concatenation technique

and the best known locally testable codes.

Our local correction result, which is significantly more involved,

also uses random concatenation, along with a number of further ideas:

the Guruswami-Sudan-Indyk list decoding strategy for concatenated codes,

Alon-Edmonds-Luby distance amplification, and the

local list-decodability, local list-recoverability and local testability

of Reed-Muller codes.

Curiously, our final local correction algorithms go via local

list-decoding and local testing algorithms; this seems

to be the first time local testability is used in the

construction of a locally correctable code.