Abstract
In this talk we will discuss how two key techniques stemming from statistical physics can be applied to solve a variant of the notorious Unique Games Problem, potentially opening new avenues towards the Unique Games Conjecture. The variant, which we call Count-Unique Games, is a promise problem where in the "yes" case we are guaranteed to have a certain (relatively small) number of highly satisfiable assignments to the Unique Games instance. We note that in the standard Unique Games problem, the "yes" case only guarantees at least one such good assignment. We exhibit efficient algorithms based on approximating a suitable partition function for the Unique Games instance based on (i) a zero-free region and polynomial interpolation, and (ii) the cluster expansion, to solve Count-UGC for certain interesting ranges of parameters. We also pose the question of when Count-UGC is equivalent to UGC.