Past Meetup

PWL#9 => Leif Walsh on Level Ancestor Simplified

This Meetup is past

62 people went

Location image of event venue


Leif Walsh ( , engineer at Tokutek ( (and from PWL NYC (, comes to visit us! Leif will present the Level Ancestor Simplified ( paper by Bender and Farach-Colton.

Leif tells us: " 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 (, 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!"

Note: If you can't get enough of Tree Data Structures Leif will also be presenting on Wednesday, November 12 at Heavybit. RSVP here for: A Deep Dive on On-Disk Data Structures, B-Trees, LSM-Trees and Fractal Trees ( We hope to see you there too!!

Leif's Bio

Leif Walsh (@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.

Meeting mechanics

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

After the paper is presented, we will open up the floor for discussion and questions.

We have selected a post meetup bar! After the meetup we'll head to Mars bar ( (798 Brannan St) to have some drinks.