[talks] Dan Larkin will present his Pre FPO on Tuesday, December 9 at 3pm in CS 301 (updated)
ngotsis at CS.Princeton.EDU
Mon Dec 8 11:20:04 EST 2014
Dan Larkin will present his Pre FPO on Tuesday, December 9, 2014 at 3pm in CS 301.
The members of his committee are:
Robert Tarjan (advisor), Jeff Erickson and Robert Sedgewick (readers), and Zeev Dvir and Sanjeev Arora.
Everyone is invited to attend his talk. The talk title and abstract follow below:
Compressing Trees with a Sledgehammer
A number of fundamental algorithms make use of the compressed tree framework to accelerate computation on graphs and sets. Perhaps the most well-known of these problems is disjoint set union (union-find). The main contributions of this disseration are a simple, optimal, randomized solution to the disjoint set union problem; an optimal, space-saving solution to the nested variation of the same problem; and a clean, unified analysis which encapsulates virtually all known optimal compressed tree algorithms and provides significant flexibility to handle a wide class of possible algorithms.
More information about the talks