On the Approximation Resistance of Balanced Linear Threshold Functions

07/12/2018
by   Aaron Potechin, et al.
0

In this paper, we show that there exists a balanced linear threshold function (LTF) which is unique games hard to approximate, refuting a conjecture of Austrin, Benabbas, and Magen. We also show that the almost monarchy predicate on k variables is approximable for sufficiently large k.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset