Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems

We extend recent techniques for time-space tradeoff lower bounds using multiparty communication complexity ideas. Using these ar-guments, for inputs from large domains we prove larger tradeoff lower bounds than previously known for general branching pro-grams, yielding time lower bounds of the form T = (n log2 n) when space S = n1, up from T = (n log n) for the best previous results. We also prove the first unrestricted separation of the power of general and oblivious branching programs by proving that 1GAP, which is trivial on general branching programs, has a time-space tradeoff of the form T = (n log2(n=S)) on oblivious branching programs. Finally, using time-space tradeoffs for branching programs, we improve the lower bounds on query time of data structures for near-est neighbor problems in d dimensions from (d = log n), proved in the cell-probe model [8, 5], to (d) or (d p log d = log log d) or even (d log d) (depending on the metric space involved) in slightly less general but more reasonable data structure models. 1