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

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

Venue: 
online
Please use this link & sign in with your real name

Lecturer:
Georg Moser
Researcher at TCS, University of Innsbruck

Abstract: 

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