Thursday, 29th of April 2021, 12:00 – 1:00

ATLAS: Automated amortised complexity analysis of self-adjusting data structures

Please use this link & sign in with your real name

Georg Moser
Researcher at TCS, University of Innsbruck


Being able to argue about the performance of self-adjusting data structures such as splay trees has been a main objective, when Sleator and Tarjan introduced the notion of *amortised* complexity. Analysing these data structures requires sophisticated potential functions, which typically contain logarithmic expressions. Possibly for these reasons, and despite the recent progress in automated resource analysis, they have so far eluded automation. In this talk, I'll report on the first fully-automated amortised complexity analysis of self-adjusting data structures.

This is joint work with Lorenz Leutgeb, David Obwaller and Florian Zuleger.


Nach oben scrollen