Collaborative Research: AF: Small: Weak Derandomizations in Time and Space Complexity

某些计算任务，如网络连接、排序和测试数字是否是质数，都允许使用省时的算法。另一方面，许多计算任务，如旅行商问题、整数分解和其他几个优化问题，都不允许使用快速算法。为什么在自然计算任务中会存在这样的计算差异？这是一个影响许多科学领域的基础性问题，包括数学、工程学、经济学、最优化和通信--这些领域超出了计算机科学。计算复杂性理论研究高效计算的概念。通常，效率是根据时间、内存和随机性等计算资源来衡量的。这个项目旨在通过研究随机性的作用及其与时间和记忆的相互作用来推进计算复杂性理论的最新发展。该项目的研究成果将在同行评议的场馆以及开放获取的场馆发表，从而能够广泛传播科学成果。将努力在研究生和本科生水平上将研究与教学相结合。尽管有强有力的科学证据表明随机计算可以有效地去随机化，但建立无条件和完全的去随机化结果是众所周知的，远远超出了该领域目前的技术。在这种情况下，这个项目将调查某些弱但无条件的去随机。这是通过探索(A)伪确定性算法--以高概率输出正规值的随机化算法，及其与复杂性理论中的一些中心主题的关系，包括完备性、承诺问题和电路复杂性；以及(B)可多次访问随机磁带的概率空间受限计算，及其与时间受限概率类的去随机化的关系来实现的。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Certain computational tasks such as network connectivity, sorting, and testing whether a number is a prime number admit time-efficient algorithms. On the other hand, many computational tasks, such as the traveling salesperson problem, integer factoring, and several other optimization problems, are not known to admit fast algorithms. Why does such computational disparity exist among natural computational tasks? This is a foundational question that impacts many scientific areas including mathematics, engineering, economics, optimization, and communication -- areas beyond computer science. Computational complexity theory investigates the notion of efficient computation. Typically, efficiency is measured in terms of computational resources such as time, memory, and randomness. This project aims to advance the state-of-the-art in computational complexity theory by investigating the role of randomness and its interplay with time and memory. Research findings from this project will be published in peer-reviewed venues as well as in open access venues enabling broad dissemination of scientific results. Efforts will be taken to integrate research with teaching at both graduate and undergraduate levels.Even though there is strong scientific evidence that randomized computations can be efficiently derandomized, establishing unconditional and complete derandomization results is known to be well beyond the current techniques in the field. In this context, this project will investigate certain weak but unconditional derandomizations. This is achieved by exploring (a) pseudodeterministic algorithms -- randomized algorithms that output a canonical value with high probability, and their relation to some central topics in complexity theory including completeness, promise problems, and circuit complexity; and (b) probabilistic space-bounded computations with multiple access to the random tape, and their relation to derandomization of time-bounded probabilistic classes.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.