文献

J-GLOBAL ID：201202261232020615   整理番号：12A0763620

リスト復号の質問計算量

Query Complexity for List Decoding

著者 (1件)： KAWACHI Akinori (Tokyo Inst. of Technol. Tokyo, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 21(COMP2012 1-7)  ページ： 1-5  発行年： 2012年04月20日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本報告ではリスト復号の質問計算量について議論を行う。我々の主結果はリスト復号のために必要な質問回数の下界証明である。より詳しく言うと,あるδ=δ(k)があって任意のq元符号C:Z_q^k→Z_qⁿと任意の定数0<γ<1に対してもしε<1/((1+δ)(q-1))ならば,リストサイズをεq^o(k)にするためには,その符号のリスト復号器は受信語の少なくとも(1-γ)(1-Hq((1-1/q)(1-(1+δ)ε)))^-1k個のブロックを(乱択的かつ適応的な方法でも)参照する必要がある,ということを証明する。特にq=o(klnk)ならばδ∈o(1)である。qとεがその条件を満たす場合,この下界は最良のリスト復号可能符号でのブロック長とほぼ一致しており,したがってこのようなパラメータ設定では受信語への局所的参照はリスト復号器が得る必要がある情報量について大きな優位性を持たない。(著者抄録)

シソーラス用語： *復号化 ,  *質問 ,  *計算量 ,  符号 ,  限界 ,  一覧表 ,  誤り訂正
準シソーラス用語： エラー訂正 ,  リスト ,  下界 ,  復号

分類 (2件)： 符号理論  (ND02030R) ,  計算理論  (JB02000A)

引用文献 (12件)：

• ELIAS, P. List decoding for noisy channels. 1957
• WOZENCRAFT, J. M. List decoding. Quarterly Progress Report. 1958, 48, 90-95
• SUDAN, M. List decoding : Algorithms and applications. SIGACT News. 2000, 31, 1, 16-27
• VADHAN, S. The unified theory of pseudorandomness. SIGACT News. 2007, 38, 3, 39-54
• GOLDREICH, O. A hard-core predicate for all one-way functions. Proceedings of the 21st ACM Symposium on Theory of Computing, 1989. 1989, 25-32

タイトルに関連する用語 (4件)： リスト ,  復号 ,  質問 ,  計算量