Reproduce “On Solving Linear Systems in Sublinear Time” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow

This research develops randomized algorithms for approximating single coordinates of solutions to Symmetric Diagonally Dominant (SDD) linear systems in polylogarithmic time. It simultaneously establishes a fundamental classical limitation, proving that general sparse, well-conditioned Positive Semidefinite (PSD) matrices require polynomial query time for such approximations, and that the condition number implies a quadratic cost for SDD matrices.

Key insights

  • Estimating individual coordinates of solutions to SDD linear systems can be done efficiently in sublinear (polylogarithmic) time on classical computers by framing the problem as a Monte Carlo random walk.
  • There exists a fundamental qualitative difference between SDD and general PSD matrices regarding local solvability: classical algorithms cannot achieve sublinear time for general sparse, well-conditioned PSD matrices when seeking specific coordinate values.
  • The condition number $\kappa(S)$ is an inherent bottleneck for classical sublinear algorithms solving SDD systems, with a quadratic dependence on $\kappa(S)$ being necessary.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.