Satisfying Degree-$d$ Equations over $GF[2]^n$
Received: June 20, 2012
Revised: July 15, 2013
Published: November 27, 2013
Download article from ToC site:
[PDF (244K)]    [PS (871K)]    [PS.GZ (265K)]
[Source ZIP]
Keywords: polynomials, probabilistically checkable proofs, constraint satisfaction, approximation
ACM Classification: F.2.2
AMS Classification: 68Q17

Abstract: [Plain Text Version]

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.