On Solving Linear Systems in Sublinear Time

Understand

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\in\mathbb{R}^n$ in the range of $S$, and the goal is to output $x\in \mathbb{R}^n$ satisfying $Sx=b$.
• For the case when the matrix $S$ is symmetric diagonally dominant (SDD), the breakthrough algorithm of Spielman and Teng [STOC 2004] approximately solves this problem in near-linear time (in the input size which is the number of non-zeros in $S$), and subsequent papers have further simplified, improved, and generalized the algorithms for this setting.
• Here we focus on computing one (or a few) coordinates of $x$, which potentially allows for sublinear algorithms.