In massive data analysis, statistical estimation needs to be carried out with close attention to computational resources -- compute cycles, communication bandwidth and storage capacity. Yet little is presently known about the fundamental tradeoffs between statistical and computational efficiency. We present recent work that revisits classical linear and nonparametric estimation theory from a computational perspective. In particular, we formulate an extension to Pinsker's theorem in the setting of rate distortion theory, and present algorithms for trading off estimation accuracy for computational speed in linear and nonparametric regression. We also revisit stochastic convex optimization from a statistical point of view, deriving new computational lower bounds. Joint work with Yuancheng Zhu and Dinah Shender of the University of Chicago.