Hardness of Solving Sparse Overdetermined Linear Systems
ACM Transactions on Computation Theory · 2009
DOI: 10.1145/1595391.1595393 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2009. Verfasst von Venkatesan Guruswami und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 13 Literaturangaben. Gefördert von: Division of Computing and Communication Foundations.
Abstract (Originalsprache)
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.
Förderung
- Division of Computing and Communication Foundations
Zitieren
APA
Guruswami, V., & Raghavendra, P. (2009). Hardness of Solving Sparse Overdetermined Linear Systems. ACM Transactions on Computation Theory. https://doi.org/10.1145/1595391.1595393
Vancouver
Guruswami V, Raghavendra P. Hardness of Solving Sparse Overdetermined Linear Systems. ACM Transactions on Computation Theory. 2009. doi:10.1145/1595391.1595393
BibTeX
@article{Guruswami2009,
author = {Guruswami, Venkatesan and Raghavendra, Prasad},
title = {Hardness of Solving Sparse Overdetermined Linear Systems},
journal = {ACM Transactions on Computation Theory},
year = {2009},
doi = {10.1145/1595391.1595393}
}
EUVIMED