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.