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

随机算法消耗一种宝贵的资源：均匀分布的随机比特。这项工作的主要焦点之一是开发设计算法的通用技术，这些算法不使用那么多随机比特。伪随机生成器将一个短的随机字符串拉伸成一个更长的字符串，对于任何多项式时间的对手来说，这个字符串看起来都是完全随机的。伪随机生成器是安全私钥密码系统的核心组件，可用于节省蒙特卡罗算法使用的随机比特数。在演示了如何从任意单向函数构造伪随机生成器之后，研究者计划开发更有效的伪随机生成器构造。计数问题的一个典型和重要的例子是估计满足给定布尔公式的真值赋值的个数。针对该问题设计了多项式时间随机化算法，并寻求多项式时间确定性算法。近年来发展起来的程序检验理论是对程序验证和程序测试的有益补充。这个理论提供了一种计算函数f的方法，并使用一个可能部分错误的程序P来验证答案的正确性。这个理论已经成功地应用于各种代数问题，将扩展到其他应用。//

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. //