Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436482 | Theoretical Computer Science | 2014 | 13 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Flavio Chierichetti, Ravi Kumar, Mohammad Mahdian,