Abstract
We will discuss how sketching tools impacted the design of fast algorithms in a variety of settings. The sketching concept has been originally proposed in the context of streaming algorithms, as a computational generalization of the classic dimension reduction method, for the purpose of reducing *space* usage. However, in recent years, sketching has been increasingly used to speed-up algorithms in, e.g., high-dimensional geometry, numerical linear algebra, iterative methods, and linear programs. A typical application of sketching proceeds by reducing either the size of the input or the size of some intermediate computations to be iterated over by an algorithm. In this talk we will survey some examples of such applications of sketching to obtain fast(er) algorithms.