TY - GEN
T1 - NP-hardness of approximately solving linear equations over reals
AU - Khot, Subhash
AU - Moshkovitz, Dana
PY - 2011
Y1 - 2011
N2 - In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each equation contains at most three variables. Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be "non-trivial". Here is an informal statement of our result: it is NP-hard to distinguish whether there is a non-trivial assignment that satisfies 1-δ fraction of the equations or every non-trivial assignment fails to satisfy a constant fraction of the equations with a "margin" of Ω(√δ). We develop linearity and dictatorship testing procedures for functions f: R n -> R over a Gaussian space, which could be of independent interest. We believe that studying the complexity of linear equations over reals, apart from being a natural pursuit, can lead to progress on the Unique Games Conjecture.
AB - In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each equation contains at most three variables. Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be "non-trivial". Here is an informal statement of our result: it is NP-hard to distinguish whether there is a non-trivial assignment that satisfies 1-δ fraction of the equations or every non-trivial assignment fails to satisfy a constant fraction of the equations with a "margin" of Ω(√δ). We develop linearity and dictatorship testing procedures for functions f: R n -> R over a Gaussian space, which could be of independent interest. We believe that studying the complexity of linear equations over reals, apart from being a natural pursuit, can lead to progress on the Unique Games Conjecture.
KW - PCP
KW - hardness of approximation
KW - linear equations
UR - http://www.scopus.com/inward/record.url?scp=79959709044&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79959709044&partnerID=8YFLogxK
U2 - 10.1145/1993636.1993692
DO - 10.1145/1993636.1993692
M3 - Conference contribution
AN - SCOPUS:79959709044
SN - 9781450306911
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 413
EP - 419
BT - STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing
PB - Association for Computing Machinery
T2 - 43rd ACM Symposium on Theory of Computing, STOC 2011
Y2 - 6 June 2011 through 8 June 2011
ER -