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.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11573/545281
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
social impact