Pseudorandomness and Fault Tolerance

PI：Zuckerman，David I.机构：德克萨斯大学奥斯汀分校建议编号：9912428摘要关于伪随机性和容错性之间的联系，最近有一些有趣的结果。这个项目进一步研究了这些联系。在伪随机性中，该项目研究了抽取器、去随机化空间有界计算、组合矩形的伪随机生成器和伪随机排列。列表上的每一项都适用于以下项。在容错方面，该项目研究了完美信息和密码模型中的随机计算，以及与抽取器相关的纠错码的方面。

PI: Zuckerman, David I.Institution: U of Texas AustinProposal Number: 9912428AbstractThere have been interesting recent results on the connection between pseudo-randomness and fault-tolerance. This project investigates these connections further.In psudo-randomness, the project investigates extractors, derandomizing space-bounded computations, pseudorandom generators for combinatorial rectangles and pseudorandom permutations. Each item on the list has an application to the following item. In fault-tolerance, the project investigates randomized computation in the perfect infomation and cryptographic models, and aspects of error-correcting codes related to extractors.