In this paper we study the complexity of the following feasibility problem: given an n × 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-distance at least n2 - ε{lunate} from every similarity that admits an LSH. We complement this hardness result by providing an over(O, ̃) (3n) algorithm for the LSH feasibility problem, which improves upon the naïve nΘ (n) time algorithm; we prove that this running time is tight, modulo constants, under the Exponential Time Hypothesis. © 2014 Elsevier B.V. All rights reserved.
The complexity of LSH feasibility / Chierichetti, Flavio; Ravi, Kumar; Mohammad, Mahdian. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 530:(2014), pp. 89-101. [10.1016/j.tcs.2014.02.030]
The complexity of LSH feasibility
CHIERICHETTI, FLAVIO;
2014
Abstract
In this paper we study the complexity of the following feasibility problem: given an n × 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-distance at least n2 - ε{lunate} from every similarity that admits an LSH. We complement this hardness result by providing an over(O, ̃) (3n) algorithm for the LSH feasibility problem, which improves upon the naïve nΘ (n) time algorithm; we prove that this running time is tight, modulo constants, under the Exponential Time Hypothesis. © 2014 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
