Speaker: Robert Krauthgamer

Affiliation: Weizmann Institute of Science

Title: On Solving Linear Systems in Sublinear Time

Abstract:

I will discuss sublinear algorithms that solve linear systems locally. In

the classical version of this problem, the input is a matrix S and a vector

b in the range of S, and the goal is to output a vector x satisfying Sx=b.

We focus on computing (approximating) one coordinate of x, which potentially

allows for sublinear algorithms. Our results show that there is a

qualitative gap between symmetric diagonally dominant (SDD) and the more

general class of positive semidefinite (PSD) matrices. For SDD matrices, we

develop an algorithm that runs in polylogarithmic time, provided that S is

sparse and has a small condition number (e.g., Laplacian of an expander

graph). In contrast, for certain PSD matrices with analgous assumptions, the

running time must be at least polynomial.

Joint work with Alexandr Andoni and Yosef Pogrow.