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

           Vikas K. Garg                Tamar Pichkhadze
             MIT                      MIT
         vgarg@csail.mit.edu              tamarp@alum.mit.edu

                        Abstract
     We resolve the fundamental problem of online decoding with general nth order er-
     godic Markov chain models. Specifically, we provide deterministic and randomized
     algorithms whose performance is close to th ...