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

随机化算法消耗一种宝贵的资源： 分布的随机比特。 这项工作的主要重点之一是 开发设计算法的通用技术， 使用尽可能多的随机位。 伪随机生成器将一个短随机字符串扩展为一个长随机字符串。 在任何多项式时间内看起来完全随机的更长的字符串 对手。 伪随机发生器是 安全的私钥密码系统，并可用于保存 蒙特卡罗算法使用的随机位数。 已经示出 如何从任何单向函数构造伪随机生成器， 研究人员计划开发更多的建筑， 高效的伪随机发生器 计数问题的一个典型而重要的例子是估计 满足给定布尔公式的真值赋值的数量。 为此设计了一个多项式时间的随机算法 问题，并将寻求一个多项式时间确定性算法。 近年来，程序检测理论的发展， 是对程序验证和程序测试的有益补充。这 理论，它提供了一种计算函数f和验证 答案的正确性使用可能部分错误的 一个程序P，用来计算f。 这一理论， 成功地应用于各种代数问题，将 扩展到其他应用程序。 //

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