A "sketch" is a data structure supporting some pre-specified set of queries and updates to a database while consuming space substantially (often exponentially) less than the information theoretic minimum required to store everything seen. Thus sketching can be seen as some form of functional compression. The advantages of sketching include reduced memory consumption, faster algorithms, and reduced bandwidth requirements in distributed computing environments.
Sketching has been a core technique in several domains, including processing massive data streams with low memory footprint, 'compressed sensing' for lossy compression of signals with few linear measurements, and dimensionality reduction or 'random projection' methods for speedups in large-scale linear algebra algorithms, and high-dimensional computational geometry.
This talk will provide a glimpse into some recent progress on core problems in the theory of sketching algorithms.
