1 h 15 min
Asynchronous Concurrency in Data Structures | Richard M. Karp Distinguished Lecture
Parallel Computing, Distributed Computing and Computer Science seminar by Robert Tarjan, Princeton University
Hosted by Simons Institute for the Theory of Computing, UC Berkeley
Tuesday 15:30 Los Angeles (GMT-7)
Recording available
Berkeley, United States
Recording
Abstract
Robert Tarjan asks how much data-structure operations can be accelerated using multiple unsynchronised processes. The presentation examines the challenges of exploiting concurrency through joint work with Siddhartha Jayanti on efficient concurrent disjoint-set union. It includes recent approaches that remove the need for randomisation.
Topics
data-structure operationsunsynchronised processesconcurrencyconcurrent disjoint-set uniondisjoint-set unionSiddhartha Jayantirandomisation
Related seminars
Introduction to Data Structures and Optimization for Fast Algorithms | Richard M. Karp Distinguished Lecture
Video · 1 h 9 min · Captions · Sep 5, 2023Aaron Sidford, Stanford UniversityAcceleration and Adaptive Selection in Asynchronous Iterative Solvers
Video page · May 5, 2026Evan Coleman, University of Mary WashingtonAsynchronous preconditioners and linear solvers
Video page · May 5, 2026Erik Boman, Sandia National Laboratories
More from Simons Institute for the Theory of Computing, UC Berkeley
All talksOptimal Spectral Gaps | Richard M. Karp Distinguished Lecture
Oct 14, 2026Ramon van HandelMy Favorite Expanders | Richard M. Karp Distinguished Lecture
Sep 29, 2026Ryan O'DonnellEncrypting to a Mathematical Fact | Theoretically Speaking
Video · 1 h 24 min · Captions · Jul 15, 2026Sanjam GargResponsibly Improving AI with Privacy-Sensitive Data: Principles, Theory, and Practice | Richard M. Karp Distinguished Lecture
Video · 1 h 10 min · Captions · Feb 24, 2026Brendan McMahan
Upcoming in Parallel Computing
All seminarsAsync and Parallel R: Building the Open Source Tools
Oct 22, 2026Charlie Gao