Exploring the unique games conjecture
Motivation
At some point during my Masters degree I was prompted with a choice; a project route, or a thesis route. If I could go back in time I would talk some sense into myself and convince younger-me to just do the project! Jokes aside, my thesis was one of the most difficult journeys of my life and I am very proud of my accomplishments, and very happy that it is behind me at the same time.
I've always been very interested in the complexity of algorithms and discovering new ways of efficiency, which is why I approached the advanced algorithms professor about advising. We spoke for a bit, and he recommended studying a conjecture by mathematician Subhash Khot. I was very intrigued and started exploring this conjecture that simply put, states that it may not be possible to find an efficient solution to some problems regardless of how good your algorithm may be. More importantly though, this conjecture states that it might not even be possible to find an efficient approximation to some problems, specifically problems that aren't guaranteed a solution. I use multiple commonly known computing problems to explore the depth of their solution space and even try to put genetic algorithms to the test to try and understand the evolutionary method to solve these problems more efficiently.
My thesis changed who I am as a software engineer. It radically changed my methods of thinking from a stance of improving on my baseline, to trying new things in the search for better solutions. I will be a better engineer because of it and I'm thankful that I had this experience even though it was a stress inducing nightmare for a significant period of time.
I've always been very interested in the complexity of algorithms and discovering new ways of efficiency, which is why I approached the advanced algorithms professor about advising. We spoke for a bit, and he recommended studying a conjecture by mathematician Subhash Khot. I was very intrigued and started exploring this conjecture that simply put, states that it may not be possible to find an efficient solution to some problems regardless of how good your algorithm may be. More importantly though, this conjecture states that it might not even be possible to find an efficient approximation to some problems, specifically problems that aren't guaranteed a solution. I use multiple commonly known computing problems to explore the depth of their solution space and even try to put genetic algorithms to the test to try and understand the evolutionary method to solve these problems more efficiently.
My thesis changed who I am as a software engineer. It radically changed my methods of thinking from a stance of improving on my baseline, to trying new things in the search for better solutions. I will be a better engineer because of it and I'm thankful that I had this experience even though it was a stress inducing nightmare for a significant period of time.
Abstract
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 as possibly better approximate algorithms that can usually save time and money. Most CSPs were classified as NP-complete and NP-Hard in the seventies, and since then computationally tractable approximate solutions has come about with the possibility of solving these using machine learning algorithms. CSPs are relevant and can directly impact and improve daily situations. We design a random game to study three CSPs to gain a better understanding of Khot’s Conjecture or UGC.