Copy

Toshiya ITOH, Yasuhiro SUZUKI, "Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 2, pp. 263-270, February 2010, doi: 10.1587/transinf.E93.D.263.

Abstract: A (*k*,δ,ε)-locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N} is an error-correcting code that encodes =(*x*_{1},*x*_{2},...,*x*_{n}) ∈ **F**_{q}^{n} to *C*() ∈ **F**_{q}^{N} and has the following property: For any ∈ **F**_{q}^{N} such that *d*(,*C*()) ≤ δ *N* and each 1 ≤ *i* ≤ *n*, the symbol *x*_{i} of can be recovered with probability at least 1-ε by a randomized decoding algorithm looking at only *k* coordinates of . The efficiency of a (*k*,δ,ε)-locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N} is measured by the code length *N* and the number *k* of queries. For a *k*-query locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N}, the code length *N* was conjectured to be exponential of *n*, i.e., *N*=exp(*n*^{Ω(1)}), however, this was disproved. Yekhanin [In Proc. of STOC, 2007] showed that there exists a 3-query locally decodable code *C*:**F**_{2}^{n} **F**_{2}^{N} such that *N*=exp(*n*^{1/log log n}) assuming that infinitely many Mersenne primes exist. For a 3-query locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N}, Efremenko [ECCC Report No.69, 2008] further reduced the code length to *N*=exp(*n*^{O((log log n/ log n)1/2)}), and in general showed that for any integer *r*>1, there exists a 2^{r}-query locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N} such that *N*=exp(*n*^{O((log log n/ log n)1-1/r)}). In this paper, we will present improved constructions for query-efficient locally decodable codes by introducing a technique of "composition of locally decodable codes," and show that for any integer *r*>5, there exists a 9 2^{r-4}-query locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N} such that *N*=exp(*n*^{O((log log n/ log n)1-1/r)}).

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.263/_p

Copy

@ARTICLE{e93-d_2_263,

author={Toshiya ITOH, Yasuhiro SUZUKI, },

journal={IEICE TRANSACTIONS on Information},

title={Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length},

year={2010},

volume={E93-D},

number={2},

pages={263-270},

abstract={A (*k*,δ,ε)-locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N} is an error-correcting code that encodes =(*x*_{1},*x*_{2},...,*x*_{n}) ∈ **F**_{q}^{n} to *C*() ∈ **F**_{q}^{N} and has the following property: For any ∈ **F**_{q}^{N} such that *d*(,*C*()) ≤ δ *N* and each 1 ≤ *i* ≤ *n*, the symbol *x*_{i} of can be recovered with probability at least 1-ε by a randomized decoding algorithm looking at only *k* coordinates of . The efficiency of a (*k*,δ,ε)-locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N} is measured by the code length *N* and the number *k* of queries. For a *k*-query locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N}, the code length *N* was conjectured to be exponential of *n*, i.e., *N*=exp(*n*^{Ω(1)}), however, this was disproved. Yekhanin [In Proc. of STOC, 2007] showed that there exists a 3-query locally decodable code *C*:**F**_{2}^{n} **F**_{2}^{N} such that *N*=exp(*n*^{1/log log n}) assuming that infinitely many Mersenne primes exist. For a 3-query locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N}, Efremenko [ECCC Report No.69, 2008] further reduced the code length to *N*=exp(*n*^{O((log log n/ log n)1/2)}), and in general showed that for any integer *r*>1, there exists a 2^{r}-query locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N} such that *N*=exp(*n*^{O((log log n/ log n)1-1/r)}). In this paper, we will present improved constructions for query-efficient locally decodable codes by introducing a technique of "composition of locally decodable codes," and show that for any integer *r*>5, there exists a 9 2^{r-4}-query locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N} such that *N*=exp(*n*^{O((log log n/ log n)1-1/r)}).},

keywords={},

doi={10.1587/transinf.E93.D.263},

ISSN={1745-1361},

month={February},}

Copy

TY - JOUR

TI - Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length

T2 - IEICE TRANSACTIONS on Information

SP - 263

EP - 270

AU - Toshiya ITOH

AU - Yasuhiro SUZUKI

PY - 2010

DO - 10.1587/transinf.E93.D.263

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E93-D

IS - 2

JA - IEICE TRANSACTIONS on Information

Y1 - February 2010

AB - A (*k*,δ,ε)-locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N} is an error-correcting code that encodes =(*x*_{1},*x*_{2},...,*x*_{n}) ∈ **F**_{q}^{n} to *C*() ∈ **F**_{q}^{N} and has the following property: For any ∈ **F**_{q}^{N} such that *d*(,*C*()) ≤ δ *N* and each 1 ≤ *i* ≤ *n*, the symbol *x*_{i} of can be recovered with probability at least 1-ε by a randomized decoding algorithm looking at only *k* coordinates of . The efficiency of a (*k*,δ,ε)-locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N} is measured by the code length *N* and the number *k* of queries. For a *k*-query locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N}, the code length *N* was conjectured to be exponential of *n*, i.e., *N*=exp(*n*^{Ω(1)}), however, this was disproved. Yekhanin [In Proc. of STOC, 2007] showed that there exists a 3-query locally decodable code *C*:**F**_{2}^{n} **F**_{2}^{N} such that *N*=exp(*n*^{1/log log n}) assuming that infinitely many Mersenne primes exist. For a 3-query locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N}, Efremenko [ECCC Report No.69, 2008] further reduced the code length to *N*=exp(*n*^{O((log log n/ log n)1/2)}), and in general showed that for any integer *r*>1, there exists a 2^{r}-query locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N} such that *N*=exp(*n*^{O((log log n/ log n)1-1/r)}). In this paper, we will present improved constructions for query-efficient locally decodable codes by introducing a technique of "composition of locally decodable codes," and show that for any integer *r*>5, there exists a 9 2^{r-4}-query locally decodable code *C*:**F**_{q}^{n} **F**_{q}^{N} such that *N*=exp(*n*^{O((log log n/ log n)1-1/r)}).

ER -