Past Meetup

PWL#7: The LCA Problem Revisited

This Meetup is past

31 people went

Whitepages

1301 5th Avenue #1600 · Seattle, WA

How to find us

Use the 4th Ave entrance, up to 3rd floor and take elevator to 16 floor.

Location image of event venue

Details

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