Hardness of Approximating the Closest Vector Problem with Pre-Processing.
Mikhail AlekhnovichSubhash KhotGuy KindlerNisheeth K. VishnoiPublished in: FOCS (2005)
Keyphrases
- preprocessing
- feature vectors
- preprocessing step
- phase transition
- computational complexity
- post processing
- information theoretic
- data pre processing
- feature extraction
- np hard
- data points
- worst case
- nearest neighbor
- sparse matrix
- pre processed
- learning theory
- vector space
- databases
- multiresolution
- image sequences
- feature selection
- information retrieval