Optimal Fine-grained Hardness of Approximation of Linear Equations

The problem of solving linear systems is one of the most fundamental problems in computer science, where given a satisfiable linear system $(A,b)$, for $A \in $\mathbb{R}$^{n \times n}$and$b \in $\mathbb{R}$^n$,wewishtofindavector$x \in $\mathbb{R}$^n$suchthat$Ax = b$. The current best algorithms for solving dense linear systems reduce the problem to matrix multiplication, and run in time $O(n^{\omega })$. We consider the problem of finding $\epsilon$-approximate solutions to linear systems with respect to the $L_2$-norm, that is, given a satisfiable linear system $(A \in $\mathbb{R}$^{n \times n}, b \in $\mathbb{R}$^n)$,findan$x \in $\mathbb{R}$^n$suchthat$||Ax - b||_2 \leq \varepsilon||b||_2$. Our main result is a fine-grained reduction from computing the rank of a matrix to finding $\epsilon$-approximate solutions to linear systems. In particular, if the best known $O(n^{\omega })$ time algorithm for computing the rank of $n\times O(n)$ matrices is optimal (which we conjecture is true), then finding an $\epsilon$-approximate solution to a dense linear system also requires $\tilde{\mathrm{\Omega }}(n^{\omega })$ time, even for $\epsilon$ as large as $(1-1\mathrm{/}\text{poly}(n))$. We also prove (under some modified conjectures for the rank-finding problem) optimal hardness of approximation for sparse linear systems, linear systems over positive semidefinite matrices, well-conditioned linear systems, and approximately solving linear systems with respect to the $L_p$-norm, for $p \geq 1$. At the heart of our results is a novel reduction from the rank problem to a decision version of the approximate linear systems problem. This reduction preserves properties such as matrix sparsity and bit complexity.