Uses and Simulation of Randomness: Applications to Cryptography,Program Checking and Counting Problems.

点击翻译按钮获取中文摘要

Randomized algorithms consume a valuable resource: uniformly distributed random bits. One of the primary focuses of this work is to develop general techniques for designing algorithms which do not use as many random bits. A pseudo-random generator stretches a short random string into a much longer string that looks totally random to any polynomial time adversary. A pseudo-random generator is the central component in a secure private key cryptosystem, and can be used to conserve on the number of random bits used by Monte Carlo algorithms. Having shown how to construct a pseudo-random generator from any one way function, the investigator plans to develop constructions for even more efficient pseudo-random generators. A typical and important example of a counting problem is to estimate the number of truth assignments that satisfy a given boolean formula. A polynomial time randomized algorithm has been designed for this problem, and a polynomial time deterministic algorithm will be sought. Recently, the theory of program checking has developed which is a useful supplement to program verification and program testing. This theory, which provides a way of computing a function f and verifying the correctness of the answer using a possibly partially faulty program P that supposedly computes f. This theory, which has been successfully applied to a variety of algebraic problems, will be extended to other applications. //