Tata Institute of Fundamental Research
A Data Structure Lower Bound and The Peak-to-Average Lemma
STCS Student Seminar
Speaker:
Suhail Sherif
Organiser:
Vidya Sagar Sharma
Date:
Friday, 12 Apr 2019, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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
| Speaker: | Suhail Sherif |
| Organiser: | Vidya Sagar Sharma |
| Date: | Friday, 12 Apr 2019, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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
[1] https://arxiv.org/abs/1703.03575