Improving the Runtime of Algorithmic Polarization of Hidden Markov Models

Vincent Bian, Rachana Madhukara

We improve the runtime of the linear compression scheme for hidden Markov sources presented in a 2018 paper of Guruswami, Nakkiran, and Sudan. Under the previous scheme, compressin…