The complexity of LSH feasibility

In this paper we study the complexity of the following feasibility problem: given an n×nn×n similarity matrix S as input, is there a locality sensitive hash (LSH) for S? We show that the LSH feasibility problem is NP-hard even in the following strong promise version: either S admits an LSH or S   is at ℓ1ℓ1-distance at least n2−ϵn2−ϵ from every similarity that admits an LSH. We complement this hardness result by providing an O˜(3n) algorithm for the LSH feasibility problem, which improves upon the naïve nΘ(n)nΘ(n) time algorithm; we prove that this running time is tight, modulo constants, under the Exponential Time Hypothesis.