On the hardness of approximating Max-Satisfy

Max-Satisfy is the problem of finding an assignment that satisfies the maximum number of equations in a system of linear equations over Q. We prove that unless NP⊂BPP Max-Satisfy cannot be efficiently approximated within an approximation ratio of 1/n1−ɛ, if we consider systems of n linear equations with at most n variables and ɛ>0 is an arbitrarily small constant. Previously, it was known that the problem is NP-hard to approximate within a ratio of 1/nα, but 0<α<1 was some specific constant that could not be taken to be arbitrarily close to 1.