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

EAGER：AF：协作研究：时间和空间复杂性中的弱去随机化

• 批准号: 1849048
• 负责人: Vinodchandran Variyam
• 金额: $ 5万
• 依托单位: University of Nebraska-Lincoln
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2020-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1849048&HistoricalAwards=false
• 关键词: EAGER; AF; Collaborative; Research; Weak

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.

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