Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

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

Ofir Geri ofirgeri at
Tue Oct 2 14:44:08 PDT 2018

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!


Sketching Algorithms
Jelani Nelson
Harvard University

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

More information about the theory-seminar mailing list