Cray Colloquium: Sketching Algorithms
The computer science colloquium takes place on Mondays from 11:15 a.m. - 12:15 p.m.
This week's talk is part of the Cray Distinguished Speaker Series. This series was established in 1981 by an endowment from Cray Research and brings distinguished visitors to the Department of Computer Science & Engineering every year.
This week's speaker is Jelani Nelson from the University of California, Berkeley.
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, and thus can also be seen as some form of functional compression. A "streaming algorithm" is simply a data structure that maintains a sketch dynamically as data is updated. The advantages of sketching include less memory consumption, faster algorithms, and reduced bandwidth requirements in distributed computing environments. Despite decades of work in the area, some of the most basic questions still remain open or were only resolved recently. In this talk, I survey recent results across a variety of sketching topics.
Biography
Jelani Nelson is Professor in the Department of EECS at UC Berkeley. His research interests include sketching and streaming algorithms, dimensionality reduction, compressing sensing, and randomized linear algebra. He has been a recipient of the PECASE award, a Sloan Research Fellowship, and an NSF CAREER award. He is also the Founder and President of a 501(c)(3) nonprofit, "AddisCoder Inc.", which organizes annual summer camps that have provided algorithms training to over 500 high school students in Ethiopia.
Online - Zoom link