课题基金 / 基金详情

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

CCRI: Planning: Algorithmically Updating Repository of Reductions in Fine-Grained Complexity
CCRI:规划:通过算法更新减少细粒度复杂性的存储库
批准号:
1925583
负责人:
Erik Demaine
金额:
$10.0万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2019
资助国家:
美国
项目状态:
已结题
起止时间:
2019-10-01 至 2021-03-31

项目摘要

项目成果

Erik Demaine的其他基金

相似基金

相关文献

中文摘要
翻译
该项目开发了一个社区维护的中央存储库,用于记录计算问题之间的减少。这种基础结构使理论计算机科学家能够跟踪每个问题的进展和最知名的结果。细粒度复杂性是计算复杂性理论的一个最新分支,其目标是了解哪些计算问题可以在线性时间内解决(所需时间与问题规模成正比),哪些计算问题基本上需要二次时间(时间与问题规模的平方成正比),等等。这一领域的基础是约简,它展示了如何将一种类型的问题转化为另一种类型的问题,从而证明这些问题类型之间的关系。通过以机器可理解的形式记录约简及其属性,该项目使算法能够生成问题之间最著名的关系。这些自动衍生的约简可以增强我们对算法和硬度结果的认识,并让人们发现他们的知识差距,从而确定未来的研究方向。拟议的基础设施可能会改变研究细粒度复杂性的方式,更广泛地说,是理论计算机科学。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
BIGDATA: Collaborative Research: F: Making Big Data Accessible on Personal Devices: Big Network Algorithms, External Memory, and Data Streams
AF: Medium: Collaborative Research: General Frameworks for Approximation and Fixed-Parameter Algorithms
CDI-Type I: Geometric Algorithms for Staged Nanomanufacturing
海外基金