这是一篇关于伪随机性的调查,伪随机性是一种理论,它可以有效地生成看起来随机的对象,尽管它们的构造很少或根本没有随机性。这一理论对计算机科学和数学中的许多领域都有重要意义,包括计算复杂性、算法、密码学、组合学、通信和加数理论。我们的治疗特别强调已经发现的各种基本伪随机对象之间的密切联系,这些伪随机对象乍看起来在本质上非常不同:扩展器图、随机性提取器、列表可解码纠错码、采样器和伪随机生成器。演示文稿的结构是为了适合研究生水平的课程教学,每章都有练习。
理论计算机科学的基础和趋势®:第7卷:第1-3期,第1-336页,现已出版,2012年12月。[PDF][现在正式版本]。
我的课程CS225:伪随机性的课堂讲稿和习题集(以上专著基于此)