Alex Andoni
Sketching as a Tool for Fast Algorithm Design
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.