Computer Science/Discrete Mathematics Seminar I
On the Approximation Resistance of Balanced Linear Threshold Functions
Constraint satisfaction problems (CSPs) are a central topic of study in computer science. A fundamental question about CSPs is as follows. Given a CSP where each constraint has the form of some predicate P and almost all of the constraints can be satisfied, is there a randomized polynomial time algorithm which is guaranteed to do significantly better in expectation than a random assignment? If so, then we say that the predicate P is approximable. If not, then we say that P is approximation resistant.
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.