On the Optimality of the Dimensionality Reduction Method

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