BARC Distinguished Lecture by Robert Tarjan

On Thursday 7 June 2018, Turing Award Winner and elected ACM Fellow Professor Robert Tarjan is visiting BARC at the Department of Computer Science, University of Copenhagen and will give a lecture at the H.C. Ørsteds Institute followed by an informal reception in the institute's south end.

This is the first in a series of talks by renowned researchers which BARC will host and we look forward to welcoming Professor Tarjan as our first speaker at BARC Distinguished Lectures.

Title

Finding and Verifying Dominators in Flow Graphs

Abstract

Given a directed graph with a start vertex s from which all other vertices are reachable, a vertex v dominates a vertex w if v is on every path from s to w. Computing dominators is a key step in optimizing compilers and has applications in other areas such as the study of food webs. Although the problem is easy to state, efficient algorithms use deep ideas including depth-first search and disjoint set union. This talk will review work on the problem by the speaker and his colleagues over the last four decades.

Bio

Robert E. Tarjan, the James S. McDonnell Distinguished University Professor of Computer Science, joined Princeton in 1985. He received doctoral and master’s degrees in computer science from Stanford in 1972 and 1971, respectively, after earning a bachelor’s in mathematics from Caltech. His academic experience involved assistant professorships at Cornell and Stanford, and a Miller research fellowship at UC, Berkeley. Professor Tarjan’s extensive involvement in the private sector includes past and continuing fellowship, research and scientific roles at the NEC Research Institute, Princeton; InterTrust Technologies, Sunnyvale, CA; Compaq Computer, Houston, TX; Hewlett-Packard, Palo Alto, CA; and Microsoft, Mountain View, CA. His honors include Caltech’s Distinguished Alumni Award in 2010, the 2009 Edelman Award from INFORMS (member of winning H-P team), fellow of the Society for Industrial and Applied Mathematics (2009), and the Blaise Pascal Medal in Mathematics and Computer Science from the European Academy of Sciences in 2004. Professor Tarjan was the first winner of the Rolf Nevanlinna Prize, established in 1982 and awarded every four years for outstanding contributions in mathematical aspects of information sciences by the International Mathematical Union.