In 2008, Raghavendra proved a dichotomy theorem for the hardness of CSPs. Either a standard semidefinite program (SDP) gives a better approximation ratio than a random assignment or it is unique games hard to do so. However, for any given CSP it may be extremely hard to decide which case holds. In fact, it is not even known whether it is decidable!
The main result of this work is that there exists a balanced linear threshold function (LTF) which is unique games hard to approximate, refuting a conjecture of Austrin, Benabbas, and Magen. This work also shows that the almost monarchy predicate on k variables is approximable for sufficiently large k.
In this talk, I will describe Raghavendra's dichotomy theorem and illustrate it with two important examples, 3-SAT and the majority predicate. I will then describe how to construct a predicate which is a balanced LTF and is unique games hard to approximate.