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

传统上，计算复杂性理论将问题分为易处理或难处理，这取决于是否确实存在解决问题的多项式时间算法(“P与NP”)。然而，近年来，人们认识到这些类别过于粗糙，无法描述现代大数据应用时代的易处理性，这促使了细粒度复杂性理论的提出，最近又回答了是否存在近线性时间算法可以解决足够接近的近似问题的问题。这个职业项目的目标是为几个基本问题的近似算法开发一种细粒度复杂性理论。这些问题不仅在算法设计研究中具有重要的理论意义，而且在生物信息学、图像比较、在线匹配等领域也具有重要的实际应用价值。该教育计划包括开发新的教材，指导本科生和研究生，以及组织工作坊。该项目专注于算法设计中的一类问题，即度量匹配问题。研究小组将研究这一类的一个主要样本--近似编辑距离(及其最大化对应的最长公共子序列)，作为研究运载机距离、均方根距离和动态时间扭曲等问题的一般方法。我们的目标是开发一个新的框架，为P中的问题提供可能的复杂性-近似质量权衡边界的更清晰的图景，并理解算法性能在哪里是可以实现的，或者被强时间指数假设(SEH)排除的。该项目有望通过探索抽象图形中的匹配问题与将这些图形嵌入具体指标之间的新联系来促进对这些长期悬而未决的问题的理解。该奖项反映了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.