The 2018 Paris C. Kanellakis Memorial Lecture


"Algorithms: Theory meets Practice"

Robert E. Tarjan, Princeton University/Intertrust Technologies

Thursday, December 6 2018 at 4:00 P.M.

Room 368 (CIT 3rd Floor)

Theory has an important role to play in computing practice. The faster speeds and larger memory sizes of current computers vastly increase the size of the design space of possible solutions for even simple problems. A theoretical approach to algorithm design helps to systematically explore this space. Such an approach can produce algorithms that are correct and efficient as well as simple to program. I shall illustrate these points with one or two real-life examples.

Robert E. Tarjan is the Distinguished University Professor of Computer Science at Princeton University and Chief Scientist of Intertrust Technologies. He received his B.S. from the California Institute of Technology in 1969 and his M. S. and Ph.D. from Stanford University in 1971 and 1972. He has held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, HP, and Microsoft. Among other honors, he received the Nevanlina Prize in Informatics, given by the International Mathematical Union, in 1982, the A.C.M. Turing Award in 1986, and the A. C. M. Paris Kanellakis Award in Theory and Practice in 1999, the last together with Daniel Sleator for their invention of splay trees. He is a member of the National Academy of Sciences and the National Academy of Engineering, and a Fellow of the American Philosophical Society and the American Academy of Arts and Sciences. He has published over 250 papers, mostly in the areas of the design and analysis of data structures and graph and network algorithms. In 2018 he was named one of the “50 Most Influential Living Computer Scientists” by

* * * * * * * * * * * * * * *

This lecture series honors Paris Kanellakis, a distinguished computer scientist who was an esteemed and beloved member of the Brown Computer Science Department. Paris joined the Computer Science Department in 1981 and became a full professor in 1990. His research area was theoretical computer science, with emphasis on the principles of database systems, logic in computer science, the principles of distributed computing and combinatorial optimization. He died in an airplane crash on December 20,1995, along with his wife, Maria Teresa Otoya, and their two young children, Alexandra and Stephanos Kanellakis.

* * * * * * * * * * * * * * *

A reception will follow.

Host: Professor Philip Klein