PWL#7: The LCA Problem Revisited

This time Ankur Chauhan will present the paper: The LCA Problem Revisited by Michael A. Bender and Martin Farach-Colton. The lowest common ancestor problem was first stated in 1973 and it took 11 years before an optimal solution was discovered, and another 16 before an understandable and implementable solution with the same bounds was presented. This deceptively simple problem comes together in the end and uses techniques that are powerful in plenty of other places.

Link to the paper: http://www.ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf