Sparse approximations, iterative methods, and faster algorithms for matrices and graphs

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.Cataloged from PDF version of thesis.Includes bibliographical references (pages 435-460).This thesis aims to advance our algorithmic understanding of some of the most fundamental objects in computer science: graphs and matrices. Specifically, on one hand, we develop a broad set of sampling techniques that yield better (sparser) approximations of these objects and do so more efficiently. On the other hand, we provide faster algorithms for a host of core problems in numerical linear algebra and graph algorithms. The resulting insights often lead to first in decades progress on the studied problems.by Michael Benjamin Cohen.Ph. D