Asynchronous Concurrency in Data Structures | Richard M. Karp Distinguished Lecture

This talk will explore the question of whether and by how much operations on data structures can be sped up by using multiple unsynchronized processes. Taking advantage of concurrency in this setting is a challenge. The talk will describe work by Siddhartha Jayanti and Robert E. Tarjan on the efficiency of concurrent disjoint set union algorithms, including recent unpublished work that uses new ideas to eliminate the need for randomization.

Robert E. Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He has held academic positions at Cornell, UC Berkeley, Stanford, and NYU, as well as industrial research positions at Bell Labs, NEC, HP, Microsoft, and Intertrust Technologies. He has invented or co-invented many of the most efficient known data structures and graph algorithms. He was awarded the first Nevanlinna Prize from the International Mathematical Union, in 1982, for “outstanding contributions to mathematical aspects of information science,” the Turing Award in 1986 with John Hopcroft for “fundamental achievements in the design and analysis of algorithms and data structures,” and the Paris Kanellakis Theory and Practice Award in 1999 with Daniel Sleator for the invention of splay trees. He is a member of the U.S. National Academy of Sciences, the U.S. National Academy of Engineering, the American Academy of Arts and Sciences, and the American Philosophical Society. He has published more than 200 papers in high-quality refereed journals and more than 100 papers in refereed conference proceedings, and he holds 38 U.S. patents.

Refreshments will be served at 3 p.m., before the event.

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.

The lecture recording URL will be emailed to registered participants. This URL can be used for immediate access to the livestream and recorded lecture. Lecture recordings will be publicly available on SimonsTV about five days following each presentation unless otherwise noted.

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.