Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR14-107 | 30th October 2014 23:46

Locally Correctable and Testable Codes Approaching the Singleton Bound

RSS-Feed




Revision #2
Authors: Or Meir
Accepted on: 30th October 2014 23:46
Downloads: 530
Keywords: 


Abstract:

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.


Revision #1 to TR14-107 | 10th August 2014 17:07

Locally Correctable and Testable Codes Approaching the Singleton Bound





Revision #1
Authors: Or Meir
Accepted on: 10th August 2014 17:07
Downloads: 581
Keywords: 


Abstract:

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.


Paper:

TR14-107 | 10th August 2014 16:35

Locally Correctable and Testable Codes Approaching the Singleton Bound





TR14-107
Authors: Or Meir
Publication: 10th August 2014 16:44
Downloads: 408
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint