On Solving Linear Systems in Sublinear Time

Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow

We study \emph{sublinear} algorithms that solve linear systems locally. In the classical version of this problem the input is a matrix $S\in {\mathbb{R}}^{n\times n}$ and a vector $b…