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

合作研究：AF：小：时间和空间复杂性的弱去随机化

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

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.

某些计算任务，例如网络连接，分类和测试一个数字是否是质量数量的算法。另一方面，许多计算任务，例如旅行销售人员问题，整数保理和其他几个优化问题，都不知道快速算法。为什么自然计算任务之间存在这种计算差异？这是一个基本问题，影响了许多科学领域，包括数学，工程，经济学，优化和交流 - 计算机科学以外的领域。计算复杂性理论研究了有效计算的概念。通常，效率是根据计算资源（例如时间，内存和随机性）来衡量的。该项目旨在通过调查随机性及其与时间和记忆的相互作用的作用来推动计算复杂性理论的最先进。该项目的研究结果将在经过同行评审的场地以及开放式访问场所发表，从而可以广泛传播科学结果。将努力将研究与研究生和本科级别的教学融合在一起。在这种情况下，该项目将调查某些弱但无条件的衍生物。这是通过探索（a）假胜驱动算法的 - 随机算法以高概率输出规范值的随机算法，以及它们与复杂性理论中某些中心主题的关系，包括完整性，承诺问题和电路复杂性； （b）具有多个随机磁带的概率构造的空间约束计算，以及它们与时间结合的概率类别的关系的关系。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的智力优点和更广泛的影响审查标准通过评估来进行评估的。