The complexity of LSH feasibility
From MaRDI portal
Publication:2440169
DOI10.1016/J.TCS.2014.02.030zbMATH Open1359.68122OpenAlexW2013468894MaRDI QIDQ2440169FDOQ2440169
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Similarity estimation techniques from rounding algorithms
- Title not available (Why is that?)
- Factoring polynomials with rational coefficients
- The ellipsoid method and its consequences in combinatorial optimization
- The NP-Completeness of Edge-Coloring
- On the complexity of \(k\)-SAT
- Title not available (Why is that?)
- Locality-sensitive hashing scheme based on \(p\)-stable distributions
- A Note on Extreme Correlation Matrices
- Range of correlation matrices for dependent Bernoulli random variables
- Title not available (Why is that?)
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Min-wise independent permutations
- The cut cone,L1 embeddability, complexity, and multicommodity flows
- Low-distortion embeddings of general metrics into the line
- Approximation algorithms for embedding general metrics into trees
- Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
- Title not available (Why is that?)
- Title not available (Why is that?)
- Constructing Small Sample Spaces Satisfying Given Constraints
- Testing Properties of Sets of Points in Metric Spaces
- LSH-preserving functions and their applications
Cited In (2)
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)
