On the Optimality of the Dimensionality Reduction Method

We investigate the optimality of (1+epsi)-approximation algorithms obtained via the dimensionality reduction method. We show that: any data structure for the (1 + epsi)-approximate nearest neighbor problem in Hamming space, which uses constant number of probes to answer each query, must use n^{Omega(1/epsi2)} space; any algorithm for the (1 + epsi)-approximate closest substring problem must run in time exponential in 1/epsi^{2 - gamma} for any gamma > 0 (unless 3SAT can be solved in sub-exponential time). Both lower bounds are (essentially) tight