The complexity of LSH feasibility

DOI10.1016/J.TCS.2014.02.030MaRDI QIDQ2440169zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The distortion of locality sensitive hashing
• On the Distortion of Locality Sensitive Hashing
• LSH-preserving functions and their applications
• LSH-preserving functions and their applications
• Locality-sensitive hashing without false negatives

Cites work

• scientific article; zbMATH DE number 3134390 (Why is no real title available?)
• scientific article; zbMATH DE number 5506208 (Why is no real title available?)
• scientific article; zbMATH DE number 2079317 (Why is no real title available?)
• scientific article; zbMATH DE number 1559577 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• A Note on Extreme Correlation Matrices
• Approximation algorithms for embedding general metrics into trees
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Constructing Small Sample Spaces Satisfying Given Constraints
• Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
• Factoring polynomials with rational coefficients
• LSH-preserving functions and their applications
• Locality-sensitive hashing scheme based on \(p\)-stable distributions
• Low-distortion embeddings of general metrics into the line
• Min-wise independent permutations
• On the complexity of \(k\)-SAT
• Range of correlation matrices for dependent Bernoulli random variables
• Similarity estimation techniques from rounding algorithms
• Testing Properties of Sets of Points in Metric Spaces
• The NP-Completeness of Edge-Coloring
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(2)

• The distortion of locality sensitive hashing
• On the Distortion of Locality Sensitive Hashing

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2440169)