kumano_tarou https://blog.hatena.ne.jp/kumano_tarou/ 某理論計算機科学者の研究日誌 https://kumano-tarou.hatenadiary.org/ 研究 今，Emanuele Viola の論文(Computational Complexity, 2004)を読んでいるのですが，その中に Trevisan の有名な結果*1，擬似乱数生成器(pseudorandom generator: PRG)から乱数抽出器(extractor)を構成できることの証明の解説が載っていました．案外単純だったので紹介しようと思います．この擬似乱数生成器は所謂暗号論的なものではなくて，Nisan-Wigderson タイプの derandomization に利用するためのものです．このタイプの擬似乱数生成器はクラスで計算可能な難しい関数を利用して擬似乱数生成器を構… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkumano-tarou.hatenadiary.org%2Fentry%2F20080301%2F1204361808" title=" 擬似乱数生成器から乱数抽出器へ - 某理論計算機科学者の研究日誌" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2008-03-01 17:56:48 rich https://kumano-tarou.hatenadiary.org/entry/20080301/1204361808 1.0 100%