NSF Young Investigator: Randomness in Computation

这项研究的主要焦点是随机性在计算中的作用。随机化已被证明在计算机科学的几乎所有领域都非常有用，例如蒙特卡洛模拟、密码学、分布式计算和网络结构。这些随机性的使用看起来很棒，直到人们意识到计算机并没有真正可用的随机比特。大多数计算机通过使用伪随机生成器来获得随机位。通常，这些伪随机生成器在实践中工作得很好。然而，发现不好的实例并不少见。因此，如果存在这样的生成器，找到被证明是好的生成器是很重要的。我们是否总能从有效的随机化算法中去掉随机性，而留给产生正确答案的高效确定性算法？这是一个普遍的问题，它有不同的理论公式，这取决于所使用的效率概念。由于多项式时间是最常见的效率衡量标准，因此最常见的理论公式如下：随机多项式时间(BPP)是否等于确定性多项式时间(P)？不幸的是，BPP与P问题的唯一直接进展依赖于未经证实的假设。这项工作集中在两个更具体的问题上。首先，BPP能用一个输出n比特且具有有界熵的一般弱随机信源来模拟吗？第二，RSPACE(S)=DSPACE(S)，或者更现实地说，五年后，使用比聚(S)随机比特更多的随机空间(S)算法能否在太空中确定性地模拟(S)？

The primary focus of this research is the role of randomness in computation. Randomization has proved extremely useful in almost all areas of computer science, such as Monte Carlo simulations, cryptography, distributed computing, and network constructions. These uses of randomness seem wonderful, until one realizes that computers don't have truly random bits available to them. Most computers get their random bits by using pseudo-random generators. Usually, these pseudo-random generators work well in practice. Nevertheless, it is not at all unusual to find instances where they don't. It is therefore important to find generators that are provably good, if such generators exist. Can we always remove the randomness from an efficient randomized algorithm, and be left with an efficient deterministic algorithm that produces the correct answer? This is the general problem, which has different theoretical formulations, depending on the notion of efficiency used. Since polynomial time is the most common measure of efficiency, the most common theoretical formulation is as follows: does randomized polynomial time (BPP) equal deterministic polynomial time (P)? Unfortunately, the only direct progress on the BPP vs. P question has relied on unproven assumptions. This work focuses on two more specific questions. First, can BPP be simulated using a general weak random source that outputs n bits with bounded entropy? Second, does RSPACE(S) = DSPACE(S) or, more realistically with five years, can randomized SPACE(S) algorithms that use more that poly(S) random bits be simulated deterministically in SPACE(S)?