[theory-seminar] Additional Theory Talk This Thursday (10/4): Jelani Nelson on Sketching Algorithms (3pm at Gates 104)

[Ofir Geri]

Hi all,


There will be an additional theory talk this week on Thursday (10/4), 3-4pm in Gates 104. Jelani Nelson (Harvard) will be speaking on Sketching Algorithms (see details below).


Hope to see you there!

Ofir


Sketching Algorithms
Jelani Nelson
Harvard University

ABSTRACT:
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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20181002/dc3c3c10/attachment.html>