抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ランダムに構成したオブジェクトと同じような性質をもつ“擬似ランダムな”オブジェクトを明示的に構成することは,理論計算機科学における重要な研究テーマの一つである。最近の研究成果から,いくつかの擬似ランダムオブジェクトは,共通の構造をもっていることがわかってきた。その擬似ランダムオブジェクトとは,エクスパンダグラフ,乱数抽出器,リスト復号可能符号,擬似乱数生成器,困難性増幅器である。本稿では,まず,上記の擬似ランダムオブジェクトを,リスト復号のフレームワークを用いて統一的に記述する方法を紹介する。次に,このフレームワークを利用した研究成果として,Guruswami,Umans,Vadhanの研究を紹介する。彼らの研究では,Reed-Solomon符号の一般化であるParvaresかVardy符号を用いて,拡大係数が大きいエクスパンダグラフの構成を与え,その結果,定数因子を無視すれば最適な性能をもつ乱数抽出器の構成を与えている。(著者抄録)
