文献

J-GLOBAL ID：202202294988547682   整理番号：22A0917458

挿入と削除のための局所復号可能で訂正可能な符号のための指数関数的下界【JST・京大機械翻訳】

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions

著者 (6件)： Blocki Jeremiah (Purdue University,Department of Computer Science) ,  Cheng Kuan (Peking University,Center on Frontiers of Computing Studies) ,  Grigorescu Elena (Purdue University,Department of Computer Science) ,  Li Xin (Johns Hopkins University,Department of Computer Science) ,  Zheng Yu (Johns Hopkins University,Department of Computer Science) ,  Zhu Minshen (Purdue University,Department of Computer Science)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2022  号： FOCS  ページ： 739-750  発行年： 2022年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 局所復号符号(LDC)は誤り訂正符号であり,符号語の誤りにもかかわらず,個々のメッセージ記号を迅速に回復できる。Hamming誤差に対するLDCは過去数十年間広く研究され,そこでは大きな目標は,小さなクエリ複雑性で大量の誤差から解読する必要で十分な冗長性の量を理解することである。刺激的な進歩にもかかわらず,著者らは,まだいくつかの重要パラメータ領域において満足な回答を有さない。例えば,3クーリーLDCの場合,既存の構成と下限の間のギャップは,メッセージ長における超多項式である。本研究では,Insdel LDCと呼ばれる挿入および欠失エラーに対するLDCを研究した。それらの研究は,OstrovskyとPakin-Cherniavsky(Information the the the 2015)によって開始され,これは,コードパラメータにおける小さなブローアップでHamming LDCからInsdel LDCへの還元を与えた。一方,Insdel LDCの唯一の既知の下限はHamming LDCのそれらから来るので,それらの間に分離はない。ここでは,Insdel LDCの存在に対する新しい,強い下限を証明した。特に,2クーリー線形Insdel LDCは存在せず,一定のqを持つすべてのq-query Insdel LDCの長さに対して指数関数的下限を与えることを示す。q≧3に対して,この限界はHamming LDCに対する既存の下限において指数関数的である。さらに,この指数関数的下限は,適応復号器に対して保持し,符号器と復号器が秘密ランダム性を共有する秘密鍵設定においても継続する。これはHamming LDCとInsdel LDCの間の厳密な分離を示す。また,この強い下限は,Hamming LCCからLDCへの縮小のInsdel概念に対するアナログにより,Insdel LCC(私的鍵設定を除く)の関連する概念に対しても保持されている。本技法は,Hamming LDCの解析に用いられる典型的な技法からかなり離れている,挿入と削除誤差のハード分布の繊細な設計と解析に基づいている。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 多項式 ,  冗長性 ,  復号器 ,  *指数関数 ,  アナログ系 ,  *復号化 ,  符号器 ,  線形性 ,  誤り訂正符号 ,  暗号鍵
準シソーラス用語： *下界 ,  ランダム性 ,  符号語 ,  複雑性 ,  クエリー , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (6件)： 削除 ,  復号 ,  訂正 ,  符号 ,  指数関数 ,  下界