A 3-query PCP over integers
Venkatesan Guruswami, Prasad Raghavendra · 2007
A classic result due to Haastad~hastad established that for every constant ε > 0, given an overdetermined system of linear equations over a finite field Fq 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.