ECCC-Report TR14-107https://eccc.weizmann.ac.il/report/2014/107Comments and Revisions published for TR14-107en-usThu, 30 Oct 2014 23:46:11 +0200
Revision 2
| Locally Correctable and Testable Codes Approaching the Singleton Bound |
Or Meir
https://eccc.weizmann.ac.il/report/2014/107#revision2Locally-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.Thu, 30 Oct 2014 23:46:11 +0200https://eccc.weizmann.ac.il/report/2014/107#revision2
Revision 1
| Locally Correctable and Testable Codes Approaching the Singleton Bound |
Or Meir
https://eccc.weizmann.ac.il/report/2014/107#revision1Locally-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.Sun, 10 Aug 2014 17:07:57 +0300https://eccc.weizmann.ac.il/report/2014/107#revision1
Paper TR14-107
| Locally Correctable and Testable Codes Approaching the Singleton Bound |
Or Meir
https://eccc.weizmann.ac.il/report/2014/107Locally-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.Sun, 10 Aug 2014 16:44:39 +0300https://eccc.weizmann.ac.il/report/2014/107