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

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 的法定使命，并通过使用基金会的智力优点和技术进行评估，被认为值得支持。更广泛的影响审查标准。

项目成果

Model Counting Meets Distinct Elements in a Data Stream

模型计数满足数据流中的不同元素

• DOI: 10.1145/3542700.3542721
• 发表时间: 2022-05
• 期刊: ACM SIGMOD Record
• 作者: Pavan, A.;Vinodchandran, N. V.;Bhattacharyya, Arnab;Meel, Kuldeep S.
• 通讯作者: Meel, Kuldeep S.

Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size

Delphic 集并集大小的估计：实现与流大小的独立性

• DOI: 10.1145/3517804.3526222
• 发表时间: 2022-06
• 期刊: PODS '22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
• 作者: Meel, Kuldeep S.;Chakraborty, Sourav;Vinodchandran, N. V.
• 通讯作者: Vinodchandran, N. V.

Constraint Optimization over Semirings

半环的约束优化

• DOI: 10.1609/aaai.v37i4.25522
• 发表时间: 2023-06
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Pavan, A.;Meel, Kuldeep S.;Vinodchandran, N. V.;Bhattacharyya, Arnab
• 通讯作者: Bhattacharyya, Arnab

Distinct Elements in Streams: An Algorithm for the (Text) Book

流中的不同元素：（文本）书籍的算法

• 发表时间: 2022-09
• 期刊: 30th Annual European Symposium on Algorithms (ESA 2022
• 作者: Chakraborty, Sourav;Vinodchandran, N. V.;Meel, Kuldeep S.
• 通讯作者: Meel, Kuldeep S.

On Approximating Total Variation Distance

关于近似总变异距离

• DOI: 10.24963/ijcai.2023/387
• 发表时间: 2023-08
• 期刊: International Joint Conference on Artificial Intelligence
• 作者: Bhattacharyya, Arnab;Gayen, Sutanu;Meel, Kuldeep S.;Myrisiotis, Dimitrios;Pavan, A.;Vinodchandran, N. V.
• 通讯作者: Vinodchandran, N. V.