Abstract:
Max-Satisfy is the problem of finding an assignment that satisfies the maximum number of equations in a system of linear equations over $\mathbb{Q}$. We prove that unless NP$\subseteq $BPP there is no polynomial time algorithm for the problem achieving an approximation ratio of $1/n^{1-\epsilon}$, where $n$ is the number of equations in the system and $\epsilon > 0$ is an arbitrarily small constant. Previously, it was known that the problem is NP-hard to approximate within a ratio of $1/n^\alpha$, but $0 < \alpha < 1$ was some specific constant that could not be taken to be arbitrarily close to~1.