ECCC-Report TR10-047https://eccc.weizmann.ac.il/report/2010/047Comments and Revisions published for TR10-047en-usSun, 25 Apr 2010 17:02:11 +0300
Revision 1
| Local list decoding with a constant number of queries |
Avraham Ben-Aroya,
Klim Efremenko,
Amnon Ta-Shma
https://eccc.weizmann.ac.il/report/2010/047#revision1Recently Efremenko showed locally-decodable codes of sub-exponential
length. That result showed that these codes can handle up to
$\frac{1}{3} $ fraction of errors. In this paper we show that the
same codes can be locally unique-decoded from error rate
$\half-\alpha$ for any $\alpha>0$ and locally list-decoded from
error rate $1-\alpha$ for any $\alpha>0$, with only a constant
number of queries and a constant alphabet size. This gives the first
sub-exponential codes that can be locally list-decoded with a
constant number of queries.Sun, 25 Apr 2010 17:02:11 +0300https://eccc.weizmann.ac.il/report/2010/047#revision1
Paper TR10-047
| Local list decoding with a constant number of queries |
Avraham Ben-Aroya,
Klim Efremenko,
Amnon Ta-Shma
https://eccc.weizmann.ac.il/report/2010/047Recently Efremenko showed locally-decodable codes of sub-exponential
length. That result showed that these codes can handle up to
$\frac{1}{3} $ fraction of errors. In this paper we show that the
same codes can be locally unique-decoded from error rate
$\half-\alpha$ for any $\alpha>0$ and locally list-decoded from
error rate $1-\alpha$ for any $\alpha>0$, with only a constant
number of queries and a constant alphabet size. This gives the first
sub-exponential codes that can be locally list-decoded with a
constant number of queries.Tue, 23 Mar 2010 19:26:13 +0200https://eccc.weizmann.ac.il/report/2010/047