Hardness of Solving Sparse Overdetermined Linear Systems

COMPUTER SCIENCE/DISCRETE MATH II
Topic:	Hardness of Solving Sparse Overdetermined Linear Systems
Speaker:	Venkatesan Guruswami
Affiliation:	University of Washington and Member, School of Mathematics
Date:	Tuesday, September 25
Time/Room:	10:30am - 12:30pm/S-101

---

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)