A 3-query PCP over integers

A classic result due to Haastad~hastad established that for every constant ε > 0, given an overdetermined system of linear equations over a finite field F q where each equation depends on exactly 3 variables and at least a fraction (1-ε) of the equations can be satisfied, it is NP-hard to satisfy even a fraction (1/q+ε) of the equations. In this work, we prove the analog of Håstad's result for equations over the integers (as well as the reals). Formally, we prove that for every ε,δ > 0, given a system of linear equations with integer coefficients where each equation is on 3 variables, it is NP-hard to distinguish between the following two cases: (i) There is an assignment of integer values to the variables that satisfies at least a fraction (1-ε) of the equations, and (ii) No assignmenteven of real values to the variables satisfies more than a fraction δ of the equations.

Authors

• Venkatesan Guruswami
• Prasad Raghavendra

Keywords

• hardness of approximation
• linearity testing
• probabilistically checkable proofs
• sparse linear equations