抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
本報告ではリスト復号の質問計算量について議論を行う。我々の主結果はリスト復号のために必要な質問回数の下界証明である。より詳しく言うと,あるδ=δ(k)があって任意のq元符号C:Z<sub>q</sub><sup>k</sup>→Z<sub>q</sub><sup>n</sup>と任意の定数0<γ<1に対してもしε<1/((1+δ)(q-1))ならば,リストサイズをεq<sup>o(k)</sup>にするためには,その符号のリスト復号器は受信語の少なくとも(1-γ)(1-Hq((1-1/q)(1-(1+δ)ε)))<sup>-1</sup>k個のブロックを(乱択的かつ適応的な方法でも)参照する必要がある,ということを証明する。特にq=o(klnk)ならばδ∈o(1)である。qとεがその条件を満たす場合,この下界は最良のリスト復号可能符号でのブロック長とほぼ一致しており,したがってこのようなパラメータ設定では受信語への局所的参照はリスト復号器が得る必要がある情報量について大きな優位性を持たない。(著者抄録)