TIME: 11:00 -- 12:00 am,  Thursday, November 20, 2008

PLACE: CSE 503  

SPEAKER: Kunal Talwar
         MSR Silicon Valley

TITLE: A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search



ABSTRACT: 

This work investigates a geometric approach to proving cell probe
lower bounds for data structure problems. We consider the approximate
nearest neighbor search problem on the Boolean hypercube. We show that
any (randomized) data structure for the problem that answers
c-approximate nearest neighbor search queries using t probes must use
space n^(1+(1/ct)). In particular, our bound implies that any data
structure that uses space near linear space with polylogarithmic word
size, and with constant probability gives a constant approximation to
nearest neighbor search queries must probe the data structur
\Omega(log n / log log n) times. This improves on the lower bound of
\Omega(log log d / log log log d) probes shown by Chakrabarti and
Regev for any polynomial space data structure, and the \Omega(log log
d) lower bound in Patrascu and Thorup for linear space data
structures. We show similar results for partial match and approximate
partial match. Our work relies on the geometry of the hypercube, and
bypasses the asymmetric communication complexity approaches that have
been previously used to prove data structure lower bounds. (joint work
with Rina Panigrahy and Udi Wieder)