Paper Info
Title
List Decoding with Double Samplers.
Abstract
We develop the notion of double samplers, first introduced by Dinur and Kaufman [DK17], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders. We show how double samplers give a generic way of amplifying distance in a way that enables efficient list-decoding. There are many error correcting code constructions that achieve large distance by starting with a base code C with moderate distance, and then amplifying the distance using a sampler, e.g., the ABNNR code construction [ABN+92] is such. We show that if the sampler is part of a larger double sampler then the construction has an efficient list-decoding algorithm and the list decoding algorithm is oblivious to the base code C (i.e., it runs the unique decoder for C in a black box way). 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.
Year
DOI
Venue
2018
10.5555/3310435.3310564
SODA '19: Symposium on Discrete Algorithms San Diego California January, 2019
DocType
Volume
ISSN
Journal
25
In Proc. 30th ACM-SIAM Symposium on Discrete Algorithms (SODA) (San Diego, 6-9 January), pages 2134-2153, 2019
Citations 
PageRank 
References 
0
0.34
0
Authors
5
Name
Order
Citations
PageRank
Irit Dinur1118785.67
Prahladh Harsha237132.06
Tali Kaufman349938.33
Inbal Livni Navon400.34
Amnon Ta-Shma5105377.33