log in  |  register  |  feedback?  |  help  |  web accessibility
Sketching Algorithms
Iribe Center 1116
Friday, February 22, 2019, 3:00-5:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)

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.


Jelani Nelson is Associate Professor of Computer Science and John L.
Loeb Associate Professor of Engineering and Applied Sciences at
Harvard. His main research interest is in algorithm design and
analysis, with focus on streaming algorithms, dimensionality
reduction, compressed sensing, and randomized linear algebra
algorithms. He completed his Ph.D. in computer science at MIT in 2011,
receiving the George M. Sprowls Award for best computer science
doctoral dissertations at MIT. He is the recipient of an NSF CAREER
Award, ONR Young Investigator Award, Sloan Fellowship, and
Presidential Early Career Award for Scientists and Engineers (PECASE).

This talk is organized by Brandi Adams