Daniel Larkin will present his FPO on Wednesday, 11/11/2015 at 10:00AM, 402 Computer Science. The members of his committee are: Readers: Robert Sedgewick and Jeff Erickson (University of Illinois at Urbana-Champaign); Examiners: Sanjeev Arora, Zeev Dvir and Robert Tarjan (adviser). A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk title and abstract follow below: Title: "Compressing Trees with a Sledgehammer" Abstract: A variety of problems can be solved more efficiently with the use of compressed trees. The compressed tree method is flexible and can be applied in different ways to solutions for many problems including disjoint set union, nested set union, and path evaluation. The central contribution of this thesis is a unified framework for the analysis of the compressed tree method and a meta-theorem that proves an inverse-Ackermann-type bound for a class of algorithms. The meta-theorem requires only that the compaction method be well-structured and that the other operations maintain a forest structure that admits a well-behaved rank function. These are the weakest known conditions of any analysis to-date that proves such a bound. We use the framework to give a clean, compact alternative analysis of all but one of the known efficient algorithms for disjoint set union; we provide an explicit proof of optimality for the remaining known optimal method, splicing by rank, which was left as an exercise by Tarjan and van Leeuwen [24]; we prove that a new algorithm for disjoint set union called randomized linking is optimal, giving theoretical backing for some recent experimental results; and finally we proceed to explore the nested set union problem, giving an optimal algorithm for any constant number of partitions as well as a few alternatives for the restricted case of two partitions.