23 citations · 34 across the 4 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2016★ 7 cited
Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms
Arturs Backurs, Christos Tzamos
The classic algorithm of Viterbi computes the most likely path in a Hidden Markov Model (HMM) that results in a given sequence of observations. It runs in time given a se…
cs.CC2015★ 23 cited
Quadratic-Time Hardness of LCS and other Sequence Similarity Measures
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
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 tw…