TCS+ talk: Wednesday, November 30 — Nicole Wein, DIMACS

by plustcs

The next TCS+ talk will take place this coming Wednesday, November 30th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Nicole Wein from DIMACS will speak about “Online List Labeling: Breaking the \log^2 n Barrier” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: The online list labeling problem is a basic primitive in data structures. The goal is to store a dynamically-changing set of n items in an array of m slots, while keeping the elements in sorted order. To do so, some items may need to be moved over time, and the goal is to minimize the number of items moved per insertion/deletion. When m = Cn for some constant C>1, an upper bound of O(\log^2 n) items moved per insertion/deletion has been known since 1981. There is a matching lower bound for deterministic algorithms, but for randomized algorithms, the best known lower bound is \Omega(\log n), leaving a gap between upper and lower bounds. We improve the upper bound, providing a randomized data structure with expected O(\log^{3/2} n) items moved per insertion/deletion.

Joint work with Michael Bender, Alexander Conway, Martin Farach-Colton, Hanna Komlos, and William Kuszmaul