License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.39
URN: urn:nbn:de:0030-drops-101326
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10132/
Go to the corresponding LIPIcs Volume Portal

Guruswami, Venkatesan ; Nakkiran, Preetum ; Sudan, Madhu

Algorithmic Polarization for Hidden Markov Models

pdf-format:
LIPIcs-ITCS-2019-39.pdf (0.6 MB)

Abstract

Using a mild variant of polar codes we design linear compression schemes compressing Hidden Markov sources (where the source is a Markov chain, but whose state is not necessarily observable from its output), and to decode from Hidden Markov channels (where the channel has a state and the error introduced depends on the state). We give the first polynomial time algorithms that manage to compress and decompress (or encode and decode) at input lengths that are polynomial both in the gap to capacity and the mixing time of the Markov chain. Prior work achieved capacity only asymptotically in the limit of large lengths, and polynomial bounds were not available with respect to either the gap to capacity or mixing time. Our results operate in the setting where the source (or the channel) is known. If the source is unknown then compression at such short lengths would lead to effective algorithms for learning parity with noise - thus our results are the first to suggest a separation between the complexity of the problem when the source is known versus when it is unknown.

BibTeX - Entry

@InProceedings{guruswami_et_al:LIPIcs:2018:10132,
  author =	{Venkatesan Guruswami and Preetum Nakkiran and Madhu Sudan},
  title =	{{Algorithmic Polarization for Hidden Markov Models}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{39:1--39:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10132},
  URN =		{urn:nbn:de:0030-drops-101326},
  doi =		{10.4230/LIPIcs.ITCS.2019.39},
  annote =	{Keywords: polar codes, error-correcting codes, compression, hidden markov model}
}

Keywords: polar codes, error-correcting codes, compression, hidden markov model
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI