Abstract: Column selection is an essential tool for low-rank approximation with wide-ranging applications including kernel approximation and experimental design. We present a framework for fast, efficient, and theoretically guaranteed column selection. In particular we present a sparsity-exploiting deterministic algorithm for Nyström approximation and a randomized matrix-free formalism that is well-adapted to sparse interpolative decompositions and graph kernel approximation. We bound the performance of our algorithms favorably relative to the expected performance of determinantal point process (DPP) sampling, which represents a theoretical gold standard that is difficult to realize practically. We illustrate strong real-world performance of our algorithms on a diverse set of example approximation tasks. Time permitting, we also present extensions to tensor interpolative decompositions, as well as a framework for graph Laplacian reduction, or reduced order modeling of Markov chains, based on column selection.