CAREER: Optimal Approximability

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

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.