The PI proposes to study constraint satisfaction problems like Max-Cut, Max-2-Sat, Vertex-Cover, and Chromatic-Number. For many of these problems, the boundary between efficiently-achievable approximation ratios and NP-hard approximation ratios is unknown. The PI has a 3-point plan to determine these boundaries:
1. Use recent connections between semidefinite programming algorithms, integrality gaps, and property testing to determine precise boundaries, assuming the "Unique Games Conjecture."
2. Define and explore new, more efficient property-testing--based hardness reductions.
3. Prove the Unique Games Conjecture, using the new property-testing--based reductions along with ideas from the theory of Parallel Repetition.
The broader goal of this line of research is to give more efficient and more effective algorithms for the fundamental algorithmic tasks like network partitioning, constraint satisfaction, and optimization. The PI will explore the limits of how well efficient algorithms can solve these problems. Proving "hardness results" or limitations on the capabilities of efficient computation has positive practical consequences. For one, it prevents wasted effort in trying to improve unimprovable algorithms. More importantly, by carefully isolating the aspects of algorithmic tasks which make them difficult, we are often led to new, effective algorithms for solving the tasks when these aspects are not present.
The project was concerned with developing new computer algorithms for basic optimization problems. Additionally, the project was concerned with proving that some basic optimization problems cannot be solved by any efficient computer algorithm. Results of the latter kind are important not just for delineating what can and cannot be done efficiently be computers, but for cryptography -- any computational task that cannot be solved efficiently might be used as the basis of a cryptosystem. One major outcome of the project was a complete understanding of the "Max-Cut" problem, arguably the simplest possible "constraint satisfaction problem". In the Max-Cut problem, the input is a large network (e.g., a social network, in which nodes are people and some pairs of nodes are connected by friendship). The task is to divide the nodes into two groups so that as many connections as possible are broken. It has long been known that finding the optimal division is computationally infeasible (i.e., there can be no efficient algorithm which solves the problem exactly for large enough input networks). However there were some efficient algorithms known which guarantee finding a division which achieves a certain fraction of the optimal number of breakages. In joint work with his PhD student Yi Wu (now faculty at Purdue), the PI identified a new efficient algorithm which guarantees a larger fraction of the optimum. Furthermore, the work showed that the new algorithm is best possible, under a certain assumption called the "Unique Games Conjecture". Subsequent work by Prasad Raghavendra extended this result to hold for all Constraint Satisfaction Problems, not just Max-Cut. The Unique Games Conjecture is a notorious assumption that is the subject of much current research in computer science. The PI’s project contributed to this research in several ways. One outcome was more "computational intractability" consequences of the conjecture (e.g., for machine learning problems). Another outcome involved tying the Unique Games Conjecture and the best known algorithms for attacking it to the subject of mathematical proof complexity. Other unexpected and diverse outcomes of this research included new results on the surface area of foams which fill up space (see attached illustrations) and an "open-source mathematics" collaboration on a notorious problem in combinatorics. A final major outcome of the project was the training and development of new computer science researchers. Two students (Yi Wu and Yuan Zhou) graduated from Carnegie Mellon with PhD theses based on the PI’s project, and have gone on to tenure-track research positions in computer science. The PI continues to advise several more PhD students on research topics related to the proposal.
