Abstract: In a recent breakthrough work Kasper Green Larsen, Omri Weinstein and Huacheng Yu [1] proved the first superlogartithmic lowerbound for a dynamic data structure problem. En route to this, they proved an interesting lemma that they termed the Peak-to-Average lemma. This lemma looks like it can be of independent interest, and will be the focus of this talk. We will look at the high level ideas behind the lower bound, why the lemma is needed and why the lemma is true.
[1] https://arxiv.org/abs/1703.03575
