We consider the approximate nearest neighbour search problem (ANN) on
the d-dimensional Hamming Cube. We show that a randomised cell probe
algorithm that uses polynomial storage and poly(d) word size requires a
worst case query time of $Omega(log log d / log log log d)$. The
approximation factor may be as loose as $2^{log^{1-eta} d}$ for any
fixed eta > 0. This fills a major gap in the study of ANN since all
earlier lower bounds either did not allow randomisation or did not allow
approximation.

Generalising the dimension reduction techniques in the ANN algorithm of
Kushilevitz et al., we then give a cell probe upper bound which matches
the lower bound up to a constant, for any constant approximation factor
eps > 0.

Our lower bound uses information theoretic techniques for communication
complexity, a theme that has been prominent in recent research.

Joint work with Oded Regev.