Mihai Pătraşcu (IBM Almaden)

UB CSE Theory Seminar, Fall 2008

(Data) Structures

We show that a large fraction of the data-structure lower bounds known today in fact follow by reduction from the communication complexity of lopsided (asymmetric) set disjointness! This includes lower bounds for:

• high-dimensional problems, where the goal is to show large space lower bounds.
• constant-dimensional geometric problems, where the goal is to bound the query time for space O(n.polylg n).
• dynamic problems, where we are looking for a trade-off between query and update time. (In this case, our bounds are slightly weaker than the originals, losing a lglgn factor.)

Our reductions also imply new lower bounds for range reporting, the partial match problem, and reachability oracles.