On the Approximation Resistance of Balanced Linear Threshold Functions

07/12/2018

∙

by   Aaron Potechin, et al.

∙

0

∙

share

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.