Pseudorandomness and Fault Tolerance

PI: Zuckerman, David i .机构：U of Texas austin提案编号：9912428 abstract最近关于伪随机性和容错之间的联系有一些有趣的结果。本项目进一步研究了这些联系。在伪随机中，该项目研究了提取器、非随机化空间边界计算、组合矩形的伪随机生成器和伪随机排列。列表中的每一项都对下一项有一个应用。在容错方面，该项目研究了完美信息和密码模型中的随机计算，以及与提取器相关的纠错码的各个方面。

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.