Unique games conjecture

Background

Subhash Khot, from Ichalkaranji in Maharashtra and an IIT Bombay graduate, proposed in 2002 that approximating the value of a certain kind of constraint game is NP-hard. Assuming it, the best known approximation algorithms for problems such as Max-Cut and Vertex Cover turn out to be optimal.

Significance

Organised a large part of approximation theory around one question. Khot received the 2014 Nevanlinna Prize; a 2018 proof of the related 2-to-2 games conjecture was a major step toward it.

Fair to say

Still a conjecture: it is neither proved nor disproved.

Path to modern innovation

Guides which approximation algorithms are worth searching for.

Builds on

• 1992PCP theorem and hardness of approximation

Global impact

• Proofs of optimal inapproximability for many problems, conditional on the conjecture.

References

• 3On the power of unique 2-prover 1-round games S. Khot, 2002

Further reading

• 1Wikipedia: Unique games conjecture
• 2Wikipedia: Subhash Khot