Improving the Runtime of Algorithmic Polarization of Hidden Markov Models

Abstract

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, compressing a message of length $n$ takes $O(n\log n)$ runtime, and decompressing takes $O(n^{1+\delta })$ runtime for any fixed $\delta >0.$ We present how to improve the runtime of the decoding scheme to $O(n\log n)$ by caching intermediate results to avoid repeating computation.

6 pages. arXiv admin note: text overlap with arXiv:1810.01969 by other authors