#7 => Leif Walsh on The LCA Problem Revisited

We're elated to have Leif Walsh (http://leifwalsh.com/), engineer at Tokutek (http://www.tokutek.com/), presenting on The LCA Problem Revisited (http://www.ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf) by Michael A. Bender and Martin Farach-Colton.

Intro

My favorite problems are always those with the highest ratio of difficulty in solving to difficulty in stating. The lowest common ancestor problem exemplifies this. It was first stated in 1973 (http://dl.acm.org/citation.cfm?doid=800125.804056), and can be described to anyone in two sentences, or with one sentence and a picture. But 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, in this paper, The LCA Problem Revisited. This problem is furthermore satisfying because its bounds are so tight: pre-processing takes as long as just reading the input, and queries are constant time.

The LCA Problem Revisited is a wonderfully curated journey through a deceptively simple problem that comes together in the end in a beautiful way, and it uses techniques that are powerful in plenty of other places. Plus, it solves another bonus problem along the way!

Bio

Leif Walsh (@leifwalsh (https://twitter.com/leifwalsh)) is a professional cat wrangler. In his free time, he works at Tokutek on Fractal Tree indexing algorithms and implementation, and building stronger distributed systems algorithms into TokuMX, the high performance distribution of MongoDB.

Details

Doors open at 7 pm; the presentation will begin at 7:30 pm; and, yes, there will be beer and pizza.

After Leif presents the paper, we will open up the floor to discussion and questions.

We hope that you'll read the paper before the meetup, but don't stress if you can't. If you have any questions, thoughts, or related information, please visit our github-thread (https://github.com/papers-we-love/papers-we-love/issues/123) on the matter.

Additionally, if you have any papers you want to add to the repository above (papers that you love!), please send us a pull request (https://github.com/papers-we-love/papers-we-love/pulls). Also, if you have any ideas/questions about this meetup or the Papers-We-Love org, just open up an issue.