Often in applications ranging from medical imaging and sensor networks to error correction and data science, one needs to solve large-scale linear systems efficiently and without loading the entire system into memory. Here, we discuss a few recent results showing that simple methods like the Kaczmarz and Stochastic Gradient Descent methods offer provable and efficient convergence, even in settings where the systems are highly corrupted. We develop several variants of iterative methods that converge to the solution of the uncorrupted system of equations, even in the presence of large corruptions. We present both theoretical and empirical results that demonstrate the promise of these iterative approaches.