A 3-query PCP over integers

ABSTRACT

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.

REFERENCES

• 1: Edoardo Amaldi , Viggo Kann, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Theoretical Computer Science, v.209 n.1-2, p.237-260, Dec. 6, 1998 [doi>10.1016/S0304-3975(97)00115-1]
• 2: Sanjeev Arora , László Babai , Jacques Stern , Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, Journal of Computer and System Sciences, v.54 n.2, p.317-331, April 1997 [doi>10.1006/jcss.1997.1472]
• 3: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 4: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 5: Eli Ben-Sasson , Madhu Sudan , Salil Vadhan , Avi Wigderson, Randomness-efficient low degree tests and short PCPs via epsilon-biased sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780631]
• 6: Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
• 7: Uriel Feige , Daniel Reichman, On the hardness of approximating Max-Satisfy, Information Processing Letters, v.97 n.1, p.31-35, 16 January 2006 [doi>10.1016/j.ipl.2005.08.012]
• 8: Vitaly Feldman , Parikshit Gopalan , Subhash Khot , Ashok Kumar Ponnuswami, New Results for Learning Noisy Parities and Halfspaces, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.563-574, October 21-24, 2006 [doi>10.1109/FOCS.2006.51]
• 9: Venkatesan Guruswami , Prasad Raghavendra, Hardness of Learning Halfspaces with Noise, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.543-552, October 21-24, 2006 [doi>10.1109/FOCS.2006.33]
• 10: M. Halldorsson. Approximations of weighted independent set and hereditary subset problems. J. Graph Algorithms Appl., 4(1), 2000.
• 11: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 12: Subhash Khot, Guest column: inapproximability results via Long Code based PCPs, ACM SIGACT News, v.36 n.2, June 2005 [doi>10.1145/1067309.1067318]
• 13: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
hardness of approximation, linearity testing, probabilistically checkable proofs, sparse linear equations