The important observation underlying this work is that there exists a quite generic transformation of families of codes that have rate arbitrary close to one and (possibly small) constant relative distance to families that have optimal relative distance (given such rate) such that this transformation preserves many naturla properties of codes. The transformation is due to Alon and Luby (1996), and was used recently by Guruswami, Indyk and Rudra [GI02, GI05, GR08]. In each of these cases, first families of the first type having some desired property were constructed, and then the transformation was applied while preserving that property. The current paper observes that this transformation preseves many additional natural properties including local-correctability and local-testability.
Note (May 2015): This work led to a new work by Or and others (see choice Nr 177), and in retrospect it is defined as a preliminary version of the later work.
Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are codes that admit local algorithms for decoding and testing respectively. The local algorithms are randomized algorithms that make only a small number of queries to their input. LCCs and LTCs are both interesting in their own right, and have important applications in complexity theory.
It is a well-known question what are the best rate and distance that such LCCs and LTCs can achieve. When discussing LCCs and LTCs that use a constant number of queries (which is the most common setting), it is known that LCCs can not achieve a constant rate, and it is believed that the same is true for LTCs. However, it has recently been discovered that the situation is radically different when using $n^{\beta}$ queries ($\beta>0$): it turns out that there are both LCCs and LTCs that achieve any constant rate, while using $n^{\beta}$ queries.
In this work, we observe that in fact, LCCs and LTCs with $n^{\beta}$ queries can, for any rate, approach the best possible relative distance. More specifically, recall that, by the Singleton bound, an error-correcting code of rate $r$ can have relative distance of at most $1-r$. We construct LCCs and LTCs that, for every $r>0$ and $\varepsilon>0$, have rate $r$ and relative distance $1-r-\varepsilon$, where the alphabet size is a constant that depends on $\varepsilon$. By applying concatenation to those codes, we obtain binary LCCs and LTCs with $n^{\beta}$ queries that achieve the Zyablov bound, which constitutes the best known parameters for (explicit) binary codes.
See ECCC TR14-107.