Journal
2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE
Volume -, Issue -, Pages 59-78Publisher
IEEE
DOI: 10.1109/FOCS.2015.14
Keywords
SETH; lower bounds; sequence alignments; parameterized complexity; LCS; DTWD
Categories
Ask authors/readers for more resources
Two important similarity measures between sequences are the longest common subsequence (LCS) and the dynamic time warping distance (DTWD). The computations of these measures for two given sequences are central tasks in a variety of applications. Simple dynamic programming algorithms solve these tasks in O(n(2)) time, and despite an extensive amount of research, no algorithms with significantly better worst case upper bounds are known. In this paper, we show that for any constant epsilon > 0, an O(n(2-epsilon)) time algorithm for computing the LCS or the DTWD of two sequences of length n over a constant size alphabet, refutes the popular Strong Exponential Time Hypothesis (SETH).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available