CompSci Talks: The LCA Problem Revisited
Leif Walsh (Developer, Tokutek) gives a presentation on 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.
This talk was given at the Papers We Love meetup in NYC at Viggle, Inc.