Unique games conjecture

Subhash Khot's conjecture asserts that a particular constraint satisfaction problem is NP-hard to approximate. If true, it implies optimal inapproximability bounds for many problems including MAX-CUT and vertex cover.

Status: half-proven (the 2-to-1 games conjecture, a closely related form, was proved in 2018). A full proof or refutation of UGC would reshape the landscape of approximation algorithms.