Abstract:
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 the speaker on the efficiency of concurrent disjoint set union algorithms, including recent unpublished work that uses new ideas to eliminate the need for randomization.

Short bio:
Robert E. Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University.  He has held academic positions at Cornell, Berkeley, Stanford, and NYU, and 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 “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 Award in Theory and Practice 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, more than 100 papers in refereed conference proceedings, and holds 38 U.S. Patents.