23 citations · 34 across the 3 of their papers we have counts for
3 papers
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…
quant-ph2012★ 4 cited
Optimal quantum query bounds for almost all Boolean functions
Andris Ambainis, Arturs Backurs, Juris Smotrovs +1
We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of…