AF: Small: Analysis, Geometry, and Hardness of Approximation

点击翻译按钮获取中文摘要

Algorithms are systematic procedures to solve computational problems. There are a class of problems called "NP-hard" problems which are believed to be computationally infeasible or "hard", and without any efficient algorithms. A well-known representative problem in this class is the Travelling Salesperson (TSP) problem: given a large number of cities and pairwise distances among them, what is the minimum length tour that visits all the cities? NP-hard problems, though computationally hard, do arise in practice and do need to be "solved" somehow. A natural approach is to design efficient algorithms that compute approximate solutions along with a guarantee on the quality of approximation. In the case of TSP, there is an efficient algorithm that computes a tour that is guaranteed to be at most 1% longer than the minimum length tour (which might be good enough in practice). A huge amount of research has been devoted to designing good approximation algorithms for numerous NP-hard problems. However, it is also of interest to investigate whether there are limitations on the quality of approximation that can be achieved by an efficient algorithm. Indeed, it turns out that for several NP-hard problems, computing an approximation better than a specific threshold is as hard as computing the exact solution (and hence infeasible). These latter kind of results, called "hardness of approximation" results, are the focus of this project. The project aims at studying analytic and geometric questions that are motivated by their applications to theoretical computer science (TCS) and primarily to hardness of approximation. The research goals of the proposal will be integrated with teaching, mentoring, and dissemination activities.Hardness of approximation has been a highly influential topic of research starting with the Probabilistically Checkable Proofs (PCP) Theorem in early 1990s. While there have been major successes towards characterizing precise approximation thresholds for basic NP-hard problems, this quest remains largely open. The investigator for this project proposed the Unique Games Conjecture (UGC) in 2002 to make further progress, which turned out to be quite successful, and led to many novel research directions. This project focuses on (1) the analytic and geometric questions that arise from the investigator's recent work towards proving the UGC; (2) understanding the phenomenon of approximation resistance of predicates (which would certainly lead to challenging analytic questions and would likely be related to the recently resolved Dichotomy Conjecture); (3) analytic questions that are not necessarily related to hardness of approximation, but are among long-term goals in this area at the interface of analysis, geometry, and hardness of approximation.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.