Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms
Authors: Arturs Backurs, Christos Tzamos
ICML 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our lower bounds are based on assumptions that the best known algorithms for the All-Pairs Shortest Paths problem (APSP) and for the Max-Weight k-Clique problem in edge-weighted graphs are essentially tight. Finally, using a recent algorithm by Green Larsen and Williams for online Boolean matrix-vector multiplication, we get a 2Ω( log n) speedup for the Viterbi algorithm when there are few distinct transition probabilities in the HMM. In this work, we attempt to explain this apparent barrier for faster runtimes by giving evidence of the inherent hardness of the Viterbi Path problem. In particular, we show that getting a polynomial speedup would imply a breakthrough for fundamental graph problems. Our lower bounds are based on standard hardness assumptions for the All-Pairs Shortest Paths and the Min-Weight k-Clique problems and apply even in cases where the number of distinct observations is small. |
| Researcher Affiliation | Academia | 1MIT, US. |
| Pseudocode | Yes | For every query vector v, we perform the following: Sort indices i1, ..., in such that vi1 ... vin in O(n log n) time. Partition the indices into p = 2α log n sets, where set Sk contains indices i(k 1) n p +1, ..., ik n . Set r = ( , ..., )T , where indicates an undefined value. For k = 1...p fill the entries of r as follows: Let ISk be the indicator vector of Sk that takes value 1 at index i if i Sk and 0 otherwise. Compute the Boolean matrix-vector product πk = A ISk using the algorithm from Theorem 9. Set rj = mini Sk(Aj,i + vi) for all j [n] such that rj = and πk j = 1. Return vector r. |
| Open Source Code | No | No explicit statement or link to open-source code is provided. |
| Open Datasets | No | The paper is theoretical and does not involve training models on datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for validation. |
| Hardware Specification | No | No specific hardware used for experiments is mentioned, as this is a theoretical paper. |
| Software Dependencies | No | No specific software dependencies with version numbers are mentioned, as this is a theoretical paper. |
| Experiment Setup | No | No experimental setup details like hyperparameters or training settings are provided, as this is a theoretical paper. |