### DIMACS Theoretical Computer Science Seminar

Title: Tight Bounds for Approximate Nearest Neighbour Search

Speaker: **Amit Chakrabarti**, Dartmouth College

Date: March 22, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

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.

See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html