[Theory] Fwd: Fw: UPDATED Department of Computer Science Bulletin: Upcoming Events starting Friday January 15

[Ali Vakilian]

Hi all,

Jelani Nelson is giving a talk tomorrow at NU distinguished lecture series
which could be of interest to you. Please see the announcement below.

Best,
Ali

---------- Forwarded message ---------
From: Samir Khuller <samir.khuller at northwestern.edu>
Date: Tue, Jan 19, 2021 at 1:34 PM
Subject: Fw: UPDATED Department of Computer Science Bulletin: Upcoming
Events starting Friday January 15
To: Ali Vakilian <vakilian at ttic.edu>



Please forward to TTIC friends.

Samir Khuller
Peter and Adrienne Barris Professor and Chair
Computer Science Department
R.R. McCormick School of Engineering and Applied Sciences
3017 Seeley Mudd
Northwestern University

------------------------------


*WEDNESDAY / CS Distinguished Lecture Series *
*January 20  / 12:00 pm *

“Sketching Algorithms”

Jelani Nelson, UC Berkeley



Zoom:
https://northwestern.zoom.us/j/99265312096?pwd=VGZTZjhBa2Vva2ZOMTc5SHpKMFJkQT09
<https://urldefense.com/v3/__https://northwestern.zoom.us/j/99265312096?pwd=VGZTZjhBa2Vva2ZOMTc5SHpKMFJkQT09__;!!Dq0X2DkFhyF93HkjWTBQKhk!G7FOlKQoTQDpovX9280i3CJJHLAGbDKqg2K87dpVNdyeHkAB4GO-Lb4YG5hQnJ126_tkPa09$>

Livestream:
https://northwestern.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=dd081a99-5e70-4c48-9536-acb1010b70d0
<https://urldefense.com/v3/__https://northwestern.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=dd081a99-5e70-4c48-9536-acb1010b70d0__;!!Dq0X2DkFhyF93HkjWTBQKhk!G7FOlKQoTQDpovX9280i3CJJHLAGbDKqg2K87dpVNdyeHkAB4GO-Lb4YG5hQnJ126xx4ylrT$>

*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. The advantages of sketching include less memory consumption,
faster algorithms, and reduced bandwidth requirements in distributed
computing environments. Work on sketching and streaming started in the late
70s and early 80s with algorithms such as the Morris approximate counter,
Flajolet-Martin probabilistic counting (“distinct elements”), the
Munro-Paterson rank/ select algorithms, and the Misra-Gries ‘Frequent’
algorithm, paused for a bit until the mid 1990s, and has maintained steam
again since the 1996 work of Alon, Matias, and Szegedy. 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
wide variety of sketching topics, some old and some new.



*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. In the past 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20210119/398fc2b6/attachment-0001.html>