__
TR09-020 | 2nd March 2009 00:00
__

#### Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.

**Abstract:**
A classic result due to Hastad established that for every constant \eps > 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-\eps) of the equations can be satisfied, it is NP-hard to satisfy even a fraction 1/q+\eps of the equations.

In this work, we prove the analog of Hastad's result for equations over the integers (as well as the reals). Formally, we prove that for every \eps,\delta > 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-\eps) of the equations, and (ii) No assignment even of real values to the variables satisfies more than a fraction \delta of the equations.