Sketching Algorithms

Talk
Jelani Nelson
Harvard University
Talk Series: 
Time: 
02.22.2019 15:00 to 17:00
Location: 

Iribe Center 1116

A "sketch" is a data structure supporting some pre-specified set ofqueries and updates to a database while consuming space substantially(often exponentially) less than the information theoretic minimumrequired to store everything seen. Thus sketching can be seen as someform of functional compression. The advantages of sketching includereduced memory consumption, faster algorithms, and reduced bandwidthrequirements in distributed computing environments.Sketching has been a core technique in several domains, includingprocessing massive data streams with low memory footprint, 'compressedsensing' for lossy compression of signals with few linearmeasurements, and dimensionality reduction or 'random projection'methods for speedups in large-scale linear algebra algorithms, andhigh-dimensional computational geometry.This talk will provide a glimpse into some recent progress on coreproblems in the theory of sketching algorithms.