  We survey key techniques and results from approximation theory in the context
of uniform approximations to real functions such as e^{-x}, 1/x, and x^k. We
then present a selection of results demonstrating how such approximations can
be used to speed up primitives crucial for the design of fast algorithms for
problems such as simulating random walks, graph partitioning, solving linear
system of equations, computing eigenvalues and combinatorial approaches to
solve semi-definite programs.
