NP-Hardness of approximately solving linear equations over reals

Subhash Khot, Dana Moshkovitz

Research output: Contribution to journalArticlepeer-review

Abstract

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 "nontrivial." Here is an informal statement of our result: it is NP-hard to distinguish whether there is a nontrivial assignment that satisfies 1-δ fraction of the equations or every nontrivial assignment fails to satisfy a constant fraction of the equations with a marginh of ω(√δ ). We develop linearity and dictatorship testing procedures for functions f : Rn → over a Gaussian space, which could be of independent interest. Our research is motivated by a possible approach to proving the unique games conjecture.

Original languageEnglish (US)
Pages (from-to)752-791
Number of pages40
JournalSIAM Journal on Computing
Volume42
Issue number3
DOIs
StatePublished - 2013

Keywords

  • Hardness of approximation
  • Linear equations
  • PCP

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'NP-Hardness of approximately solving linear equations over reals'. Together they form a unique fingerprint.

Cite this