Pseudorandomness and Fault Tolerance

University Of Texas At Austin, Austin TX

Investigators

Abstract

PI: Zuckerman, David I. Institution: U of Texas Austin Proposal Number: 9912428 Abstract There 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.