Collaborative Research: AF: Small: Fine- Grained Complexity of Approximate Problems

协作研究：AF：小：近似问题的细粒度复杂性

• 批准号: 2006806
• 负责人: Arturs Backurs
• 金额: $ 11.46万
• 依托单位: Toyota Technological Institute at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006806&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Small; Fine

Classically, an algorithm is called "efficient" if its running time is polynomial in the input size (i.e., as the input size doubles, the runtime is multiplied by some constant term). As the data becomes large, however, many such algorithms are no longer efficient in practice. For example, a quadratic-time algorithm (whose runtime grows fourfold after doubling the input size) can easily take hundreds of CPU-years on inputs of gigabyte size. For even larger inputs, the running time of a practically efficient algorithm must be effectively linear in the input size. For many problems such algorithms exist; for others, despite decades of effort, no such algorithms have been discovered yet. A recently developed theory of "fine-grained complexity" attempts to provide an explanation to this phenomenon, by identifying natural assumptions that imply that some of the existing algorithms cannot be improved. The goal of this project is to make progress on some of the key directions in this area, by developing new algorithms where possible, and showing limitations otherwise.The project will focus on approximate algorithms, because such algorithms are often very useful in practice, and their existence is often not precluded by the existing hardness results. On a high-level, the project will investigate the following topics: (1) approximate algorithms, limitations, and limitations-inspired algorithms, and (2) new hardness assumptions for improving existing hardness results. The specific goals include key computational problems over graphs, sequences and kernels.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.

传统上，如果算法的运行时间是输入大小的多项式（即，随着输入大小加倍，运行时间乘以某个常数项），则该算法被称为“高效”。然而，随着数据变大，许多此类算法在实践中不再有效。例如，二次时间算法（其运行时间在输入大小加倍后增加四倍）可以轻松地在千兆字节大小的输入上花费数百个 CPU 年。对于更大的输入，实际有效的算法的运行时间必须与输入大小有效地线性相关。对于许多问题都存在这样的算法；对于其他人来说，尽管经过了几十年的努力，仍然没有发现这样的算法。最近开发的“细粒度复杂性”理论试图通过识别意味着某些现有算法无法改进的自然假设来解释这种现象。该项目的目标是通过尽可能开发新算法并显示局限性，在该领域的一些关键方向上取得进展。该项目将重点关注近似算法，因为此类算法在实践中通常非常有用，并且现有的硬度结果通常不会排除它们的存在。在高层次上，该项目将研究以下主题：(1) 近似算法、局限性和受局限性启发的算法，以及 (2) 用于改进现有硬度结果的新硬度假设。具体目标包括图形、序列和内核的关键计算问题。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。