Streaming (Synchronous), Recursion, and Incremental Computation

Incremental computation has traditionally had an uneasy relationship with recursion/iteration. It turns out that the right operators for synchronous streaming provide a framework that elegantly supports both. This lecture presents an algebra of concurrent streaming operators that can serve as a compilation target for rich query languages on collections (the DB in DBSP). In particular, algebraic equivalences support selective incrementality because the incremental version of a query is directly definable in the algebra. For additional fun, there is a fascinating analogy with discrete signal processing (the SP in DBSP).

Val Tannen is a professor in the Department of Computer and Information Science at the University of Pennsylvania. Throughout his career, he has always been interested in applications of logic to computer science. After working for a time in programming languages, his current research interests are in databases where he and his students and collaborators have worked on query language design and on models and systems for query optimization, parallel query processing, and data integration. More recently, their work has focused on models and systems for data sharing, data provenance, the management of uncertain information, algorithmic provisioning for what-if analysis, and incremental query answer computation. Tannen has received the 20-year ICDT Test-of-Time Award and the 10-year ACM PODS Alberto O. Mendelzon Test-of-Time Award. He is an ACM fellow and a member of Academia Europaea.

===================================================================

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science, and is geared toward a broad scientific audience.

Light refreshments will be available prior to the start of the lecture. This lecture will be viewable thereafter on this page and on our YouTube channel.

The Simons Institute regularly captures photos and video of activity around the Institute for use in publications and promotional materials. 

If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.