Regression algorithms are the bread and butter of statistical data analysis, and so developing more resource-efficient regression algorithms is a pressing concern, given the ubiquity and diversity of data in many modern applications. Let us say that an algorithm runs in input-sparsity time if its running time for arbitrary (i.e., worst-case) input is proportional to the number of nonzeros of the...