AF: Small: The Unique Games Conjecture and Related Problems in Hardness of Approximation

University Of Texas At Austin, Austin TX

Investigators

Abstract

Numerous optimization problems are NP-hard and thus unlikely to have efficient algorithms. Approximation algorithms, often based on geometric techniques like linear and semidefinite programming, are so far the most successful approach against NP-hardness. This project explores their limitations, and its heart is a program towards a proof of the Unique Games Conjecture. The Unique Games Conjecture is widely recognized as the central open problem in hardness of approximation in the past two decades. Its resolution would settle the approximability of a large number of optimization problems and prove the optimality of geometric techniques. The aforementioned program towards the Unique Games Conjecture consists of two independent components. (1) Resolve the Boolean case of the Unique Games Conjecture. The investigator is collaboraing with experts in geometric functional analysis and probability in order to analyze a reduction from an NP-hard problem to Boolean unique games. This collaboration has already led to a milestone, namely an analysis of a reduction from a problem in the same spirit as NP-hard problems to Boolean Unique Games. (2) Show that the Boolean case of the Unique Games Conjecture implies the full Unique Games Conjecture. The investigator is developing techniques for "fortifying" hard Boolean unique games so they admit strong parallel repetition and imply the Unique Games Conjecture. 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.