The complexity of LSH feasibility

DOI10.1016/j.tcs.2014.02.030zbMath1359.68122OpenAlexW2013468894MaRDI QIDQ2440169

Flavio Chierichetti, Ravi Kumar, Mohammad Mahdian

Publication date: 27 March 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.02.030

zbMATH Keywords

LSHlinear duality

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

The Distortion of Locality Sensitive Hashing ⋮ On the Distortion of Locality Sensitive Hashing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
• Factoring polynomials with rational coefficients
• The ellipsoid method and its consequences in combinatorial optimization
• Min-wise independent permutations
• Testing Properties of Sets of Points in Metric Spaces
• Similarity estimation techniques from rounding algorithms
• Low-distortion embeddings of general metrics into the line
• The NP-Completeness of Edge-Coloring
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Constructing Small Sample Spaces Satisfying Given Constraints
• A Note on Extreme Correlation Matrices
• Locality-sensitive hashing scheme based on p-stable distributions
• Range of correlation matrices for dependent Bernoulli random variables
• On the complexity of \(k\)-SAT

This page was built for publication: The complexity of LSH feasibility