AF: SMALL: On the Complexity of Satisfiable CSPs

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Complexity Theory is the study of resources (time, memory, number of processors) needed to execute computational tasks, whose main goal is to classify computational problems as feasible (i.e., problems that can be solved efficiently) or as infeasible (i.e., problems that cannot be solved efficiently). Probabilistically Checkable Proofs is a sub-area of Complexity Theory that extends this study to the realm of approximation problems and shows that for many computational tasks, even coming up with an approximate solution may be computationally infeasible. Nowadays, results from this area are also used in real-life applications in non-centralized systems such as blockchains and cryptocurrencies. The goal of this project is to further develop the theory of Probabilistically Checkable Proofs and address new, as well as long-standing, challenges in the area. The project combines various branches of computer science and mathematics and may impact other scientific fields. The project's activities include course development, mentoring, and workshop organization. In more detail, this project focuses on studying satisfiable constraint satisfaction problems. The class of constraint satisfaction problems (CSPs in short) is one of the most fundamental classes of problems in complexity theory. An instance of a problem consists of a collection of undetermined variables, as well as a collection of constraints imposed on them; the goal is to find an assignment to the variables that satisfies as many of the constraints as possible. What is the best, most efficient approximation algorithm to this problem, provided that a solution that satisfies all of the constraints exists? This project is driven by this meta question, aiming to create new tools as well as form new connections with other mathematical areas. 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.