文章基本信息

标题：Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.
本地全文：下载
作者：Venkatesan Guruswami ; Prasad Raghavendra
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：A classic result due to Hastad established that for every constant \eps > 0, given an overdetermined system of linear equations over a finite field \F_q where each equation depends on exactly 3 variables and at least a fraction (1-\eps) of the equations can be satisfied, it is NP-hard to satisfy even a fraction 1/q+\eps of the equations. In this work, we prove the analog of Hastad's result for equations over the integers (as well as the reals). Formally, we prove that for every \eps,\delta > 0, given a system of linear equations with integer coefficients where each equation is on 3 variables, it is NP-hard to distinguish between the following two cases: (i) There is an assignment of integer values to the variables that satisfies at least a fraction (1-\eps) of the equations, and (ii) No assignment even of real values to the variables satisfies more than a fraction \delta of the equations.
关键词：Fourier analysis , Hastad's 3-query PCP , linearity testing , sparse linear systems