Guruswami and Vardy “Maximum-Likelihood Decoding of Reed-Solomon Codes is NP-hard” (SODA 2005). MLDは最尤復号でいいんだったかな. MLD-LinearとはF_q要素のm×n行列とシンドロームsと正整数wを入力として, Hv^t=s^tかつハミング重みがw以下となるn次の…

ようやく51問. Problem 183はそこそこ簡単だった. 先に手を動かすのが大事なのか.

Problem 59は暗号文の解読なのだが鍵が3文字で暗号文が1201文字なので, 頻度解析を行えば手でも出来る気がしてきた. XORがちょい面倒っていうくらいか.