We study the problem where we are given a system of polynomial equations defined by multivariate polynomials over $GF[2]$ of fixed, constant, degree $d>1$ and the aim is to satisfy the maximal number of equations. A random assignment approximates this number within a factor $2^{-d}$ and we prove that for any $\epsilon > 0$, it is NP-hard to obtain a ratio $2^{-d}+\epsilon$. When considering instances that are perfectly satisfiable we give a polynomial time algorithm that finds an assignment that satisfies a fraction $2^{1-d}-2^{1-2d}$ of the constraints and we prove that it is NP-hard to do better by an arbitrarily small constant. The hardness results are proved in the form of inapproximability results of Max-CSPs where the predicate in question has the desired form and we give some immediate results on approximation resistance of some predicates.

A conference version of this paper appeared in the Proceedings of APPROX 2011.