List decoding with double samplers

DOI10.1137/1.9781611975482.129MaRDI QIDQ5236316zbMATH OpenOpenAlexFDO

Authors Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.00425

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Decoding (94B35)

Abstract: We strengthen the notion of "double samplers", first introduced by Dinur and Kaufman [Proc. 58th FOCS, 2017], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders. The ABNNR code construction [IEEE Trans. Inform. Theory, 38(2):509--516, 1992] achieves large distance by starting with a base code $C$ with moderate distance, and then amplifying the distance using a sampler. We show that if the sampler is part of a larger double sampler then the construction has an efficient list-decoding algorithm. Our algorithm works even if the ABNNR construction is not applied to a base code $C$ but to any string. In this case the resulting code is approximate-list-decodable, i.e. the output list contains an approximation to the original input. Our list-decoding algorithm works as follows: it uses a local voting scheme from which it constructs a unique games constraint graph. The constraint graph is an expander, so we can solve unique games efficiently. These solutions are the output of the list decoder. This is a novel use of a unique games algorithm as a subroutine in a decoding procedure, as opposed to the more common situation in which unique games are used for demonstrating hardness results. Double samplers and high dimensional expanders are akin to pseudorandom objects in their utility, but they greatly exceed random objects in their combinatorial properties. We believe that these objects hold significant potential for coding theoretic constructions and view this work as demonstrating the power of double samplers in this context.

Recommendations

• List-Decoding with Double Samplers
• List Decoding of Direct Sum Codes
• List Decoding and Pseudorandom Constructions

Cited in

(6)

• Low-density parity-check codes achieve list-decoding capacity
• List-Decoding with Double Samplers
• scientific article; zbMATH DE number 7758327 (Why is no real title available?)
• Nearly optimal pseudorandomness from hardness
• Explicit SoS lower bounds from high-dimensional expanders
• Coboundary and cosystolic expansion from strong symmetry

This page was built for publication: List decoding with double samplers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236316)