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

计算复杂性理论根据解决自然计算问题所需的资源量，将其划分为不同的复杂性类别。典型的资源包括时间、内存、随机量和电路大小。该项目旨在利用两种以前未经测试的新技术，在理解随机性和电路大小的功率和限制方面推进最先进的技术。从这个项目中获得的直觉将增强我们对计算机科学以外领域产生的实际计算问题的理解。该项目的探索有可能解决复杂性理论中长期存在的核心问题。该项目的第一部分将通过多遍概率空间受限计算的去随机化来研究无条件地去随机化概率时间。特别是，这个项目将探索一种新的方法，以获得比目前已知的概率线性时间的渐近更好的确定性模拟。该项目的第二部分旨在通过为某些计数问题设计伪确定性近似算法来证明新的固定多项式大小的电路下界。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Computational complexity theory classifies natural computational problems into various complexity classes based on the amount of resources needed to solve them. Typical resources are time, memory, amount of randomness, and circuit size. This project aims to advance the state of the art in understanding the power and limitations of randomness and circuit size, using two new, previously untested, techniques. Intuition gained from this project will enhance our understanding of practical computational problems arising from fields beyond computer science. The project's exploration has the potential to solve central, longstanding, open questions in complexity theory. The first part of the project will investigate unconditional de-randomization of probabilistic time via de-randomization of multi-pass, probabilistic space-bounded computations. In particular, this project will explore a new approach to obtain an asymptotically better deterministic simulation of probabilistic linear time than what is currently known. The second part of this project aims to prove new fixed-polynomial size circuit lower bounds via designing pseudo-deterministic approximation algorithms for certain counting problems.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.