Revision #1 Authors: Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

Accepted on: 25th April 2010 17:02

Downloads: 1455

Keywords:

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.

TR10-047 Authors: Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

Publication: 23rd March 2010 19:26

Downloads: 1738

Keywords:

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.