The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] S-matching vectors, S-decoding polynomials(1hit)

1-1hit
  • Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length

    Toshiya ITOH  Yasuhiro SUZUKI  

     
    PAPER

      Vol:
    E93-D No:2
      Page(s):
    263-270

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