





























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 + δ})$ runtime for any fixed $δ> 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。