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:Fqn FqN is an error-correcting code that encodes =(x1,x2,...,xn) ∈ Fqn to C() ∈ FqN and has the following property: For any ∈ FqN such that d(,C()) ≤ δ N and each 1 ≤ i ≤ n, the symbol xi 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:Fqn FqN is measured by the code length N and the number k of queries. For a k-query locally decodable code C:Fqn FqN, 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:F2n F2N such that N=exp(n1/log log n) assuming that infinitely many Mersenne primes exist. For a 3-query locally decodable code C:Fqn FqN, Efremenko [ECCC Report No.69, 2008] further reduced the code length to N=exp(nO((log log n/ log n)1/2)), and in general showed that for any integer r>1, there exists a 2r-query locally decodable code C:Fqn FqN such that N=exp(nO((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 2r-4-query locally decodable code C:Fqn FqN such that N=exp(nO((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:Fqn FqN is an error-correcting code that encodes =(x1,x2,...,xn) ∈ Fqn to C() ∈ FqN and has the following property: For any ∈ FqN such that d(,C()) ≤ δ N and each 1 ≤ i ≤ n, the symbol xi 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:Fqn FqN is measured by the code length N and the number k of queries. For a k-query locally decodable code C:Fqn FqN, 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:F2n F2N such that N=exp(n1/log log n) assuming that infinitely many Mersenne primes exist. For a 3-query locally decodable code C:Fqn FqN, Efremenko [ECCC Report No.69, 2008] further reduced the code length to N=exp(nO((log log n/ log n)1/2)), and in general showed that for any integer r>1, there exists a 2r-query locally decodable code C:Fqn FqN such that N=exp(nO((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 2r-4-query locally decodable code C:Fqn FqN such that N=exp(nO((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:Fqn FqN is an error-correcting code that encodes =(x1,x2,...,xn) ∈ Fqn to C() ∈ FqN and has the following property: For any ∈ FqN such that d(,C()) ≤ δ N and each 1 ≤ i ≤ n, the symbol xi 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:Fqn FqN is measured by the code length N and the number k of queries. For a k-query locally decodable code C:Fqn FqN, 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:F2n F2N such that N=exp(n1/log log n) assuming that infinitely many Mersenne primes exist. For a 3-query locally decodable code C:Fqn FqN, Efremenko [ECCC Report No.69, 2008] further reduced the code length to N=exp(nO((log log n/ log n)1/2)), and in general showed that for any integer r>1, there exists a 2r-query locally decodable code C:Fqn FqN such that N=exp(nO((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 2r-4-query locally decodable code C:Fqn FqN such that N=exp(nO((log log n/ log n)1-1/r)).
ER -
English
