Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

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

Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers A classic result due to Håstad 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 assignment even of real values to the variables satisfies more than a fraction δ of the equations. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

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

Download PDF
20 pages

Loading next page...
 
/lp/association-for-computing-machinery/hardness-of-solving-sparse-overdetermined-linear-systems-a-3-query-pcp-aVFEqNOhwJ
Publisher
Association for Computing Machinery
Copyright
The ACM Portal is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
ISSN
1942-3454
DOI
10.1145/1595391.1595393
Publisher site
See Article on Publisher Site

Abstract

A classic result due to Håstad 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 assignment even of real values to the variables satisfies more than a fraction δ of the equations.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Sep 1, 2009

There are no references for this article.