Qi Cheng and Daqing Wan “On the List and Bounded Distance Decodability of the Reed-Solomon Codes.” (FOCS 2004, SIAM J. Comp. 37).
RS符号のリスト復号アルゴリズム (Guruswami-Sudan) の限界を超えた場合, リスト復号またはBDDが出来るかという問題を考える.
このとき, 実はリスト復号が出来るとちょっと下の有限体上の離散対数問題が解けてしまう. また上手くパラメータを設定してやると, BDDが解ければ, これまた下の有限体上の離散対数問題が解ける.
というのを今から趣味として読もうかと思っているところ. 証明追うのは出来そうな感じか.