Quadratic-Time Hardness of LCS and other Sequence Similarity Measures.
Amir AbboudArturs BackursVirginia Vassilevska WilliamsPublished in: CoRR (2015)
Keyphrases
- similarity measure
- longest common subsequence
- computational complexity
- biological sequences
- approximation algorithms
- mutual information
- dynamic time warping
- np hard
- similarity function
- edit distance
- special case
- feature vectors
- pairwise
- objective function
- search engine
- sequence analysis
- sequence matching
- evolutionary algorithm
- neural network
- machine learning methods
- learning theory
- learning classifier systems
- data mining