AF: Small: Approximability of CSPs on Satisfiable Instances

About This Grant

Theoretical Computer Science (TCS) is the study of the power and limitations of computing. The study has two complementary aspects: algorithm design, which aims at designing fast, efficient algorithms to solve computational problems, and computational complexity, which aims at rigorously showing that for some problems, no efficient algorithm exists. The famous P versus NP conjecture posits that a class of problems, known as NP-hard problems, do not have efficient algorithms. These problems, nevertheless, do arise in a wide range of practical applications and do need to be solved somehow. One way to cope with their computational hardness is to seek approximate solutions in an efficient manner, with guarantees on the quality of approximation. This has been an intensely studied topic, leading to efficient approximation algorithms for a large variety of problems and subsequent applications in theory as well as in practice. It turns out however that there are limitations on the quality of approximation that can be achieved efficiently and study of these limitations is also intensely studied. The current project aims to study the approximation question for a natural sub-class of NP-hard problems known as Constraint Satisfaction Problems. In addition to designing approximation algorithms for them and showing their limitations, the project aims at developing required mathematical tools and at answering additional long-standing questions in computational complexity and discrete mathematics. Hardness of approximation refers to the phenomenon that for several NP-hard problems, even computing approximate solutions remains an NP-hard problem. Starting with the foundational Probabilistically Checkable Proofs (PCP) Theorem in the early 1990s, there have been numerous influential results in this area. One outstanding question is to understand the approximability of Constraint Satisfaction Problems (CSPs) on satisfiable instances. That is, given a satisfiable instance of a CSP (such as 3SAT), what is the maximum fraction of constraints that can be satisfied efficiently? It is well-known that 3SAT has a sharp threshold of 7/8, meaning, there is an efficient algorithm that, on a satisfiable instance of 3SAT, finds an assignment that satisfies 7/8 fraction of the constraints and doing strictly better than this threshold is NP-hard. The project aims to characterize such a sharp threshold for every satisfiable CSP and develop required mathematical tools which would have additional applications. The investigator and his research team already have substantial results in this direction, with applications to additive combinatorics and computational complexity. The investigator foresees that the work opens up several promising research directions, morphing into a broad, long-term, impactful program. 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.