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

经典地说，如果一个算法的运行时间在输入大小中是多项式的(即，当输入大小加倍时，运行时间乘以某个常量项)，则该算法被称为“有效”。然而，随着数据变得越来越大，许多这样的算法在实践中不再有效。例如，一个二次时间算法(其运行时在将输入大小增加一倍后会增长四倍)很容易在GB大小的输入上花费数百年的CPU时间。对于更大的输入，实际有效的算法的运行时间必须与输入大小有效地线性相关。对于许多问题，这样的算法是存在的；对于另一些问题，尽管几十年的努力，但还没有发现这样的算法。最近发展起来的“细粒度复杂性”理论试图通过找出暗示某些现有算法无法改进的自然假设，来为这种现象提供解释。这个项目的目标是在这个领域的一些关键方向上取得进展，在可能的情况下开发新的算法，否则就显示出局限性。该项目将集中在近似算法上，因为这种算法在实践中通常非常有用，而且它们的存在通常不会因为现有的硬度结果而被排除在外。在高层次上，该项目将研究以下主题：(1)近似算法、限制和受限制启发的算法，以及(2)用于改善现有硬度结果的新的硬度假设。具体目标包括图形、序列和内核的关键计算问题。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.