Algorithms for solving linear equations are one of the most fundamental primitives in computer science. Formally this is the problem where, given a linear system \((A, b)\) , where \(A \in {\mathbb {R}}^{m \times n}\)  is a real matrix and \(b \in {\mathbb {R}}^m\)  is a vector in the column space of \(A\) , we need to find a vector \(x \in {\mathbb {R}}^n\)  such that \(Ax = b\) . Gaussian elimination running in timeHere we are discussing algorithms and hardness over the Real RAM, unless stated otherwise. We discuss the Word RAM in more detail in Section REF . \(O(n^3)\)  was one of the first algorithms for this problem. Hopcraft and Bunch [1]} reduced solving linear equations to fast matrix multiplication of two \(n \times n\)  matrices [2]}, [3]}, [4]}, [5]}, [6]}, [7]} which can be done in \(m(n) = n^\omega \) , where \(\omega \)  is the matrix multiplication constant. The current best known upper bound on \(\omega \)  is approximately \(2.372..\)  [7]}. The best known algorithms for solving linear systems reduce the problem to matrix multiplication, but there is no known reduction in the other direction. We study the complexity of finding approximate solutions to linear systems (defined more precisely later) under the following conjecture:
