COMPUTER SCIENCE/DISCRETE MATH II | |

Topic: | Hardness of Approximately Solving Linear Equations Over Reals |

Speaker: | Dana Moshkovitz |

Affiliation: | Member, School of Mathemtics |

Date: | Tuesday, April 27 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | https://video.ias.edu/csdm/solvoverreals |

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". We prove the hardness of the following problem: Distinguish whether there is a non-trivial assignment that satisfies 1-delta fraction of the equations or every non-trivial assignment fails to satisfy a constant fraction of the equations with a "margin" of sqrt{delta} . The hardness result matches the performance of a natural semi-definite programming-based algorithm. To prove our result, we develop linearity and dictatorship testing procedures for functions f:R^n |---> R over a Gaussian space, which could be of independent interest. Our research is motivated by a possible approach to proving the Unique Games Conjecture