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 queries ( 0"> 0 ): it turns out that there are both LCCs and LTCs that achieve any constant rate, while using n queries.

In this work, we observe that in fact, LCCs and LTCs with n 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 0"> r 0 and 0"> 0 , have rate r and relative distance 1 − r − , where the alphabet size is a constant that depends on . By applying concatenation to those codes, we obtain binary LCCs and LTCs with n queries that achieve the Zyablov bound, which constitutes the best known parameters for (explicit) binary codes.