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的法定任务，并被认为是值得通过基金会的智力优点和更广泛影响的审查审查的审查标准来通过评估来通过评估来获得支持的。