Title: Hardness of Nearest Neighbor under L-infinity
Speaker: Mihai Patrascu, AT&T
Abstract:
In FOCS'98, Indyk gave an unusual upper bound for nearest neighbor in
the L-infinity metric: a decision tree of size n^rho could compute an
approximation of O(log_rho log d) to the nearest neighbor.
We reconstruct Indyk's data structure via information-theoretic
considerations, giving a much more crisp understanding of the bound
and the structure of this space. This leads us to a matching lower
bound, via asymmetric communication complexity.