CCRI: Planning: Algorithmically Updating Repository of Reductions in Fine-Grained Complexity

CCRI：规划：通过算法更新减少细粒度复杂性的存储库

• 批准号: 1925583
• 负责人: Erik Demaine
• 金额: $ 10万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2021-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1925583&HistoricalAwards=false
• 关键词: CCRI; Planning; Algorithmically; Updating; Repository

This project develops a community-maintained central repository for recording reductions between computational problems. This infrastructure enables theoretical computer scientists to keep track of progress and the best known results for each problem. Fine-grained complexity is a recent branch of computational complexity theory where the goal is to understand which computational problems can be solved in linear time (where the time required grows proportional to the problem size), and which fundamentally require quadratic time (where the time grows as the square of the problem size), etc. The basis for this field is reductions, which show how to convert problems of one type into problems of another type, and therefore prove relations between those problem types.By recording reductions and their properties in a machine-understandable form, the project enables algorithmic generation of the best known relationships between problems. These automatically derived reductions can strengthen our knowledge of both algorithms and hardness results, and let people identify gaps in their knowledge and thereby define future research directions. The proposed infrastructure could transform the way research is done in fine-grained complexity, and more broadly, theoretical computer science.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的法定使命，并且通过使用基金会的知识价值和更广泛的影响进行评估，被认为值得支持审查标准。