CAREER: Distances and matchings under the lens of fine-grained complexity

传统上，计算复杂性理论将问题分为易处理的或难处理的，这取决于是否存在解决问题的多项式时间算法（“P vs NP”）。然而，近年来，这些类别过于粗糙，无法在现代大数据应用时代表征易处理性，这一认识激发了细粒度复杂性理论，最近，回答了是否存在近线性时间算法来解决足够接近的近似问题的问题。这个CAREER项目的目标是为一些基本问题的近似算法开发一个细粒度复杂性理论。 这些问题不仅在算法设计的研究中具有重要的理论意义，而且在生物信息学、图像比较和在线匹配等不同领域的实际应用中也很重要。 该教育计划包括开发新的教材，指导本科生和研究生，并组织研讨会。该项目侧重于算法设计中的一类问题，称为度量匹配问题。 研究小组将调查这类的主要范例，近似编辑距离（以及它的最大化对应物，最长公共子序列），作为研究地球移动器距离，均方根距离和动态时间弯曲等问题的一般方法。 我们的目标是开发一个新的框架，提供了一个更清晰的画面可能的复杂性近似质量权衡边界的问题在P和了解算法的性能是可以实现的或排除的强时间指数假设（SETH）。该项目预计将通过探索抽象图中的匹配问题与将这些图嵌入具体指标之间的新联系来促进对这些长期存在的开放问题的理解。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Traditionally, the theory of computational complexity classified problems as tractable or intractable depending on whether or not a polynomial time algorithm to solve a problem exactly exists (“P vs NP”). However, in recent years the understanding that these categories are too coarse to characterize tractability in the era of modern big data applications has motivated the theory of fine-grained complexity, and more recently, answering the question of whether a near-linear time algorithm exists that solves a close-enough approximate problem. The objective of this CAREER project is to develop a theory of fine-grained complexity for approximation algorithms for a few fundamental problems. These problems are not only of theoretical importance in the study of algorithm design but are also important in practical applications in diverse areas such as bioinformatics, image comparison, and online matching. The educational plan includes development of new teaching materials, mentoring of undergraduate and graduate students, and organizing workshops.The project focuses on a class of problems in algorithm design known as metric matching problems. The research team will investigate a primary exemplar of this class, approximate edit distance (and it's maximization counterpart, longest common subsequence), as a general approach for studying such problems as Earth Mover's Distance, Root Mean Square Distance, and Dynamic Time Warping. The goal is to develop a new framework that provides a clearer picture of the possible complexity-approximation quality tradeoff frontier for problems in P and to understand where algorithm performance is either achievable or ruled out by the Strong Time Exponential Hypothesis (SETH). The project is expected to advance the understanding of these long-standing open problems by exploring new connections between matching problems in abstract graphs and the embedding of those graphs in concrete metrics.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.