Exploring the Unique Games Conjecture
In 2002, mathematician and theoretical computer scientist Subhash Khot proposed the Unique Games Conjecture (UGC)  which has been a point of contention amongst theoretical computer scientists as they try to prove or disprove its validity. The Unique Games Conjecture is so theoretically interesting and so, in this thesis, we are going to explore its practice using a set of problems called Constraint Satisfaction Problems (CSPs). CSPs are problems that we interact with almost every day. CSPs have been studied under optimization research for a long time, and in 1950s-60s CSPs found academic focus ...
(For more, see "View full record.")