読者です 読者をやめる 読者になる 読者になる

  • STOC 2010のY. Dodis, M. Pătraşcu, M. Thorupのが面白そうだとは思わんかね。
    • A[1...n] in {0,...,9}^nなるベクトルを考える。10進n桁の整数である。計算機上(PRAMでモデル化してる)で、各桁 A[i]を読み書きする機能を高速化しつつ保存容量をなるべく小さくしたい。さてどうする?
      • 素直に2進表記した場合は保存容量は\lfloor n \cdot \log_2{10} \rfloorとなるが、読み書き機能にO(n)掛かる。
      • ハフマン符号化した場合は(ようするに各A[i]をそれぞれ2進数で表して保存)、保存容量が4n、読み書き機能はO(1)と速い。
      • いいとこどりしたのが今回の話。ここ5年位ずっとある流れですね。
      • さらに実はprefix-free codeと基数の置き換えが関連しているという話があるらしく、真面目に読みたい。DodisがいるのはMACとかに関連してくるからだそうで。
  • SHA3の話を天下一武闘会に例えると受けた。