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})})$.
著者
-
ITOH Toshiya
Global Scientific Information and Computing Center (GSIC), Tokyo Institute of Technology
-
SUZUKI Yasuhiro
Department of Information Processing, Tokyo Institute of Technology
関連論文
- 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
- Transient Central Hypothyroidisim Due to Pituitary Suppression in a Premature Neonate Born to a Mother with Three-Year-Untreated Graves' Disease
- OE-094 Decreased Susceptibility to Release of TGF-β1 from Platelet and Microalbuminuria in TXA2 Receptor Deficient Mice with Diabetes Mellitus(Diabetes/Obesity/Metabolic syndrome(01)(H),Oral Presentation(English),The 72nd Annual Scientific Meeting of the
- Primary Small Cell Carcinoma of the Common Bile Duct, in Which Surgical Treatment was Performed After Neoadjuvant Chemotherapy : Report of a Case
- Two Cases of Ductal Adenoma of the Breast
- Clinicopathological correlation between expression of PTHrP receptor and various prognostic factors in breast cancer without axillary lymph node metastasis
- Compassionate Use of Humanized Anti-HER2/neu Protein, Trastuzumab for Metastatic Breast Cancer in Japan
- Clinical Development of Trastuzumab in Breast Cancer
- Comparative Efficacy of Positron Emission Tomography and ultrasonography in Preoperative Evaluation of Axillary Lymph Node Metastases in Breast Cancer
- Autografting with peripheral blood CD34-positive cells following high-dose chemotherapy against breast cancer
- Dose-Intensified Chemotherapy for Breast Cancer: Present and Future Prospects
- PEDUNCULATED GASTRIC SIGNET RING CELL CARCINOMA
- SUCCESSFUL MANAGEMENT OF METASTASIS-INDUCED PANCREATITIS BY ENDOSCOPIC PANCREATIC DUCT STENTING IN A CASE OF LARGE CELL LUNG CANCER
- Difficulty in differential diagnosis of atypical absence seizures and complex partial seizures in childhood
- Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length
- 1PC8 Effects of carnosine and anserine supplementation on muscle energy metabolism(The Proceeding of the 14th Annual Meeting of Japan Society of Exercise and Sports Physiology July 29-30, (Hiroshima))
- Competitive Analysis of Multi-Queue Preemptive QoS Algorithms for General Priorities(Discrete Mathematics and Its Applications)
- The role of trastuzumab in the management of HER2-positive matastatic breast cancer : an updated review
- Persistent Primitive Trigeminal Artery Imaged by Three-dimensional Computed Tomography Angiography : Two Cace Reports
- Zonisamide Monotherapy in Newly Diagnosed Infantile Spasms
- IL-1β production and gene expression by peptidoglycan from Lactobacillus casei in human dental pulp cells of deciduous teeth and permanent teeth
- IL-1β production by peptidoglycan from Lactobacillus casei in human dental pulp cells of deciduous teeth and permanent teeth
- Changes in the medium-range order during crystallization of aluminosilicate zeolites characterized by high-energy X-ray diffraction technique(Aqueous Solution Science for Ceramic Processing II)
- Semi-Supervised Learning to Classify Evaluative Expressions from Labeled and Unlabeled Texts(Knowledge, Information and Creativity Support System)
- Constructing Families of ε-Approximate k-Wise Independent Permutations(Discrete Mathematics and Its Applications)
- Heterotopic Gastric Mucosa in the Gallbladder : Report of Two Cases
- Absence of the third molars in strain EL mice
- A Note on the Relationships among Certified Discrete Log Cryptosystems