Abstract We show how a "worst case to random case" reduction for high-dimensional pointsets leads to optimal hashing for approximate nearest neighbor search. Joint work with Ilya Razenshteyn. Attachment File Optimal Data-Dependent Hashing for Nearest Neighbor Search Video Recording