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.

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.

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.