Data Structure Lower Bounds 2: Static Lower Bounds via Communication Complexity

In this video, we present two different techniques for proving lower bounds for static data structures via communication complexity tools. We demonstrate the techniques on a simple problem of evaluating a polynomial and also discuss the limitations of the techniques and the largest possible lower bounds that may be proved from them. The video is part of a lecture series I gave at the Swiss Winter School on Theoretical Computer Science 2020.