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

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

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.