Theory of Computing
-------------------
Title : Satisfying Degree-$d$ Equations over $GF[2]^n$
Authors : Johan Haastad
Volume : 9
Number : 27
Pages : 845-862
URL : http://www.theoryofcomputing.org/articles/v009a027
Abstract
--------
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.