Online Markov Decoding: Lower Bounds and Near-Optimal Approximation Algorithms

Vikas K. Garg, Tamar Pichkhadze

We resolve the fundamental problem of online decoding with general $n^{th}$ order ergodic Markov chain models. Specifically, we provide deterministic and randomized algorithms whos…