Abstract
In this talk, we survey the techniques that have been proposed for proving unconditional lower bounds for dynamic data structures. We start by introducing the chronogram method of Fredman and Saks 1989, for proving logn/loglogn lower bounds. We then proceed to present the information transfer method of Patrascu and Demaine 2004, which allow us to prove logn lower bounds. After that, we present the current strongest technique, due to Larsen 2012, which allow us to prove (logn/loglogn)^2 lower bounds. We finally conclude by introducing recent work by Larsen, Weinstein and Yu 2018, which proves the first lower bounds of (logn/loglon)^(3/2) for decision problems. This improves over the best previous logn lower bounds for decision problem, due to Patrascu and Demaine 2004.