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

职业：细粒度复杂性镜头下的距离和匹配

• 批准号: 2337901
• 负责人: Aviad Rubinstein
• 金额: $ 64.6万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-06-01 至 2029-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2337901&HistoricalAwards=false
• 关键词: CAREER; Distances; matchings; under; lens

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.

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