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

Stanford University, Stanford CA

Investigators

Abstract

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.