Improving Viterbi is Hard Better Runtimes Imply Faster Clique Algorithms

ImprovingViterbiisHard:BetterRuntimesImplyFasterCliqueAlgorithmsArtursBackurs1ChristosTzamos1AbstractO(Tn2)timeforanyHMMwithnstatesandanobserva-tionsequenceoflengthT.ThisalgorithmisknownastheThecla...