Name
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: Rn - 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/1993636.1993692 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | Volume |
independent interest,unique games conjecture,gaussian space,constant fraction,linear equation,informal statement,non-trivial assignment,all-zero assignment,dictatorship testing procedure,homogeneous linear equation,linear equations,hardness of approximation | Journal | 42 |
Issue | Citations | PageRank |
3 | 6 | 0.48 |
References | Authors | |
15 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Subhash Khot | 1 | 2064 | 112.51 |
| Dana Moshkovitz | 2 | 368 | 19.14 |