Computer Science/Discrete Mathematics Seminar II

Solving a system of linear equations is a fundamental algorithmic task arising in numerous applications. It is possible to tell in polynomial time, by Gaussian elimination, if a given system admits a solution, and if so to find one. But what if the system of equations is overdetermined, and, say, only 99% of the equations can be satisfied simultaneously? The problem becomes much harder in this setting. In fact, a celebrated result of Hastad established that for every \eps > 0, given an overdetermined system of sparse linear equations over a finite field F_q with q elements, at least a fraction (1-\eps) of which can be satisfied, it is NP-hard to satisfy even a fraction (1/q+\eps) of the equations. (Note that the 1/q bound is trivially achieved by picking a solution uniformly at random.) In this work, we prove the analog of Hastad's result for equations over the rationals. Formally, we prove that 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 99.9% of the equations, and (ii) No assignment even of real values to the variables satisfies more than 0.01% of the equations. The proof is couched in a framework similar to Hastad's result, namely Fourier analysis of a Long code based test. Analyzing the test over the integers, however, involves some crucial new technical elements. The talk will recap the general PCP/Fourier analysis framework of Hastad's result, and then proceed to discussing the details of the result for equations over integers. Joint work with Prasad Raghavendra (U. Washington)