NP-hardness of approximately solving linear equations over reals

Subhash Khot, Dana Moshkovitz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 "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.

Original languageEnglish (US)
Title of host publicationSTOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing
Pages413-419
Number of pages7
DOIs
StatePublished - 2011
Event43rd ACM Symposium on Theory of Computing, STOC'11 - San Jose, CA, United States
Duration: Jun 6 2011Jun 8 2011

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other43rd ACM Symposium on Theory of Computing, STOC'11
CountryUnited States
CitySan Jose, CA
Period6/6/116/8/11

Keywords

  • PCP
  • hardness of approximation
  • linear equations

ASJC Scopus subject areas

  • Software

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

Cite this