## 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 : R^{n} → 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 language | English (US) |
---|---|

Pages (from-to) | 752-791 |

Number of pages | 40 |

Journal | SIAM Journal on Computing |

Volume | 42 |

Issue number | 3 |

DOIs | |

State | Published - 2013 |

## Keywords

- Hardness of approximation
- Linear equations
- PCP

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics