In a seminal work, Spielman and Teng [1]} gave nearly linear-time algorithms (\(O(n^2\log (1/{\varepsilon }(n)))\) -time) for finding \({\varepsilon }(n)\) -approximate solutions to Laplacian linear-systems and this result was built upon by many works [2]}, [3]} to give such algorithms for other restricted classes of linear systems. Our result shows that under the hardness of the rank-finding problem, these algorithms cannot be extended to general linear systems. As mentioned above, we conditionally rule out \(\tilde{O}(n^2)\) -time algorithms for finding \({\varepsilon }(n)\) -approximate solutions to general linear systems even for \({\varepsilon }(n) = 1-1/n^{100}\) .
