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 #1 to TR10-047 | 25th April 2010 17:02

Local list decoding with a constant number of queries

RSS-Feed




Revision #1
Authors: Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
Accepted on: 25th April 2010 17:02
Downloads: 3635
Keywords: 


Abstract:

Recently 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.


Paper:

TR10-047 | 23rd March 2010 16:08

Local list decoding with a constant number of queries





TR10-047
Authors: Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
Publication: 23rd March 2010 19:26
Downloads: 3799
Keywords: 


Abstract:

Recently 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.



ISSN 1433-8092 | Imprint