- This event has passed.
CIS Seminar: “Sketching Algorithms”
November 2 at 3:30 PM - 4:30 PM
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.
Professor, Department of Electrical Engineering and Computer Science, University of California, Berkeley
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.
For those that can not make the talk in person, Zoom link:
Meeting ID: 933 7401 2824