AF: Small: Hardness of Approximation: Classical and New

Theory of Computation (ToC) studies the fundamental nature of computation with its roots going back to logic and computability theory pioneered by Godel, Church, and Turing. In its modern form, ToC has two complementary aspects: to design efficient algorithms to solve computational problems (understanding the power of computation) and to show limitations, if any, on the efficiency that may be achieved (understanding the limits of computation).

The latter aspect is called computational complexity; it aims at demonstrating that certain computational problems cannot be solved efficiently. While computational complexity sounds like a bearer of pessimism, it does lead to deep insights into nature of computation and sometimes having computationally hard problems is actually useful and necessary (e.g., to build cryptographic systems).

A central phenomenon in computational complexity is "NP-completeness", whereby researchers strongly believe that a class of computational problems called the "NP-complete problems" have no efficient algorithms. A well-known example is the Traveling Salesperson (TSP) problem, where the input is a set of cities and all pairwise distances between them and the goal is to compute a tour that visits all the cities and traverses the minimum total distance.

It turns out that a host of problems arising in practice are NP-complete and since these do need to be solved in practice, a natural approach is to seek efficient algorithms that compute approximate solutions. The study of approximation gives rise to a further phenomenon known as "hardness of approximation", namely that many such problems turn out to be hard even to approximate.

This project aims to deepen the understanding of hardness of approximation and related mathematical tools. The project topic forms a bridge between algorithms and complexity, and also as a bridge between computer science and mathematics, especially combinatorics, analysis, and geometry. The research aspect of the project will be integrated with education (teaching courses and advising students at both undergraduate and graduate levels) and dissemination activities (research talks, writing surveys, etc.).

Starting with the foundational Probabilistically Checkable Proofs (PCP) Theorem in the early 1990s, there are numerous influential results in Hardness of Approximation, including the recent proof of the 2-to-2 Games Conjecture (by the investigator and collaborators). The project focuses on further questions in hardness of approximation and analytic tools needed to answer these questions.

It considers the classical setting of polynomial-time approximability as well as the new settings of fixed parameter tractability and fine-grained complexity. In the classical setting, the main focus of the project is to characterize approximability of Constraint Satisfaction Problems (CSPs) on satisfiable instances and developing analytic tools towards such a characterization.

To elaborate, one notes that given a satisfiable instance of a "three-satisfiability" (3SAT) problem, it is known how to efficiently find an assignment that satisfies 7/8 fraction of its clauses and moreover, that it is NP-complete to do better. The project will focus on proving analogous results for every CSP. In recent years, researchers have been making progress in neighboring areas of fixed parameter tractability and fine-grained complexity.

In fixed parameter tractability, one typically considers a problem that is known to be NP-complete (e.g. Vertex Cover) and seeks an algorithm whose running time is a (fixed) polynomial in the size of the input (e.g. the graph) and an arbitrary function of a designated parameter (e.g. the vertex cover size). In fine-grained complexity, one considers a problem that is known to have a polynomial-time algorithm, and the concern is the precise exponent of the polynomial.

In both settings, it is natural to consider approximations as well as exact solutions. In the fixed parameter setting, the project will focus on proving the analogue of the classical PCP Theorem. In the fine-grained setting, the focus will be on some geometric problems such as Closest Pair, Farthest Pair, Diameter, and Edit Distance.

The project will also study analytic questions that are not necessarily related to hardness of approximation, but are among investigator's long-term goals.

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.