Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-020 | 2nd March 2009 00:00

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


Authors: Venkatesan Guruswami, Prasad Raghavendra
Publication: 16th March 2009 07:53
Downloads: 2902


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.

ISSN 1433-8092 | Imprint