Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length
スポンサーリンク
概要
- 論文の詳細を見る
A (k, δ, ε)-locally decodable code $C:{\bf F}_{q}^{n} \rightarrow {\bf F}_{q}^{N}$ is an error-correcting code that encodes $\vec{x}=(x_{1},x_{2},\ldots,x_{n}) \in {\bf F}_{q}^{n}$ to $C(\vec{x}) \in {\bf F}_{q}^{N}$ and has the following property: For any $\vec{y} \in {\bf F}_{q}^{N}$ such that $d(\vec{y},C(\vec{x})) \leq \delta N$ and each 1 i n, the symbol xi of $ of $\vec{x}$ can be recovered with probability at least 1 - ε by a randomized decoding algorithm looking at only k coordinates of $\vec{y}$. The efficiency of a (k, δ, ε)-locally decodable code $C:{\bf F}_{q}^{n} \rightarrow {\bf F}_{q}^{N}$ is measured by the code length N and the number k of queries. For a k-query locally decodable code $C:{\bf F}_{q}^{n} \rightarrow {\bf 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:{\bf F}_{2}^{n} \rightarrow {\bf F}_{2}^{N}$ such that N=exp(n1/log log n) assuming that infinitely many Mersenne primes exist. For a 3-query locally decodable code $C:{\bf F}_{q}^{n} \rightarrow {\bf 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 2r-query locally decodable code $C:{\bf F}_{q}^{n} \rightarrow {\bf 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 · 2r-4-query locally decodable code $C:{\bf F}_{q}^{n} \rightarrow {\bf F}_{q}^{N}$ such that $N=\exp(n^{O((\log \log n/ \log n)^{1-1/r})})$.
- 2010-02-01
著者
-
SUZUKI Yasuhiro
Department of Information Processing, Tokyo Institute of Technology
-
Itoh Toshiya
Global Scientific Information And Computing Center (gsic) Tokyo Institute Of Technology
-
Suzuki Yasuhiro
Department Of Breast And Endocrine Surgery Tokai University School Of Medicine
関連論文
- Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length
- Perfusion Computed Tomography for the Indication of Percutaneous Transluminal Reconstruction for Acute Stroke
- Three-dimensional Computed Tomography Angiography of the Galenic System for the Occipital Transtentorial Approach
- Evaluation of Hyperacute Stroke Using Perfusion Computed Tomography
- Duplex Doppler Ultrasonography of Subclavian Steal Syndrome
- Adrenal Catecholamine Content in the Spontaneously Hypertensive Rats
- Enzyme Histochemical Studies on the Hypothalamus of Spontaneously Hypertensive Rates : With Special Reference to That of Rats Subjected to Various Endocrinc Interferences
- Pharmacodynamic Studies on the Cardiovascular System of Spontaneously Hypertensive Rats
- Vesicular acetylcholine transporter can be a morphological marker for the reinnervation to muscle of regenerating motor axons
- De novo Multiple Endocrine Neoplasia Type 2B with Noncardiogenic Pulmonary Edema as the Presenting Symptom