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

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

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.