Data Structure Lower Bounds

In this course we will study the main results and techniques used in proving data structure lower bounds in the well known cell-probe model.

- Cell-probe Model, Static Lower Bounds, Asymmetric Communication Complexity [Lecture Note]
- Lower Bounds using Richness Method [Lecture Note]
- Lower Bound for Approximate Nearest Neighbor Problem [Lecture Note]
- Direct-sum for Richness, Round Elimination Technique [Lecture Note]
- Cell Sampling Method and Polynomial Evaluation Problem [Lecture Note]
- Lower Bounds for Non-systematic Succinct Data Structures [Lecture Note]
- Lower Bounds for Systematic Succinct Data Structures [Lecture Note]
- Continue on Lower Bound for Succinct Partial Sums [Lecture Note]
- Dynamic Lower Bounds - The Chronogram Method [Lecture Note]
- Dynamic Lower Bounds - Information Transfer Technique [Lecture Note]
- Lower Bound for Dynamic Weighted 2D Range Counting [Lecture Note]

For any clarification regarding the course, feel free to meet me anytime at Room #324 or drop me an e-mail at <firstname> at iuuk dot mff dot cuni dot cz.