CS369E: Communication Complexity (for Algorithm Designers) Lecture #6: Data Structure Lower Bounds∗

Next we discuss how to use communication complexity to prove lower bounds on the per-formance — meaning space, query time, and approximation — of data structures. Our case study will be the high-dimensional approximate nearest neighbor problem. There is a large literature on data structure lower bounds. There are several different ways to use communication complexity to prove such lower bounds, and we’ll unfortunately only have time to discuss one of them. For example, we discuss only a static data structure problem — where the data structure can only be queried, not modified — and lower bounds for dynamic data structures tend to use somewhat different techniques. See [8, 10] for some starting points for further reading. We focus on the approximate nearest neighbor problem for a few reasons: it is obviously a fundamental problem, that gets solved all the time (in data mining, for example); there are some non-trivial upper bounds; for certain parameter ranges, we have matching lower bounds; and the techniques used to prove these lower bounds are representative of work in the area — asymmetric communication complexity and reductions from the “Lopsided Disjointness ” problem. 2 The Approximate Nearest Neighbor Problem In the nearest neighbor problem, the input is a set S of n points that lie in a metric space (X, `). Most commonly, the metric space is Euclidean space (Rd with the `2 norm). In these lectures, we’ll focus on the Hamming cube, where X = {0, 1}d and ` is Hamming distance. ∗ c©2015, Tim Roughgarden