%0 Conference Paper %1 DBLP:conf/stoc/GopalanKZ08 %A Gopalan, Parikshit %A Klivans, Adam R. %A Zuckerman, David %B STOC %D 2008 %E Ladner, Richard E. %E Dwork, Cynthia %I ACM %K codes error-correcting-codes list_decoding reed-muller %P 265-274 %R 10.1145/1374376.1374417 %T List-decoding reed-muller codes over small fields %X We present the first local list-decoding algorithm for the rth order Reed-Muller code RM(2,m) over F for r ≥ 2. Given an oracle for a received word R: Fm -< F, our randomized local list-decoding algorithm produces a list containing all degree r polynomials within relative distance (2-r - ε) from R for any ε < 0 in time poly(mr,ε-r). The list size could be exponential in m at radius 2-r, so our bound is optimal in the local setting. Since RM(2,m) has relative distance 2-r, our algorithm beats the Johnson bound for r ≥ 2. In the setting where we are allowed running-time polynomial in the block-length, we show that list-decoding is possible up to even larger radii, beyond the minimum distance. We give a deterministic list-decoder that works at error rate below J(21-r), where J(δ) denotes the Johnson radius for minimum distance δ. This shows that RM(2,m) codes are list-decodable up to radius η for any constant η < 1/2 in time polynomial in the block-length. Over small fields Fq, we present list-decoding algorithms in both the global and local settings that work up to the list-decoding radius. We conjecture that the list-decoding radius approaches the minimum distance (like over F), and prove this holds true when the degree is divisible by q-1. %@ 978-1-60558-047-0

@inproceedings{DBLP:conf/stoc/GopalanKZ08, abstract = {We present the first local list-decoding algorithm for the rth order Reed-Muller code RM(2,m) over F for r ≥ 2. Given an oracle for a received word R: Fm -< F, our randomized local list-decoding algorithm produces a list containing all degree r polynomials within relative distance (2-r - ε) from R for any ε < 0 in time poly(mr,ε-r). The list size could be exponential in m at radius 2-r, so our bound is optimal in the local setting. Since RM(2,m) has relative distance 2-r, our algorithm beats the Johnson bound for r ≥ 2. In the setting where we are allowed running-time polynomial in the block-length, we show that list-decoding is possible up to even larger radii, beyond the minimum distance. We give a deterministic list-decoder that works at error rate below J(21-r), where J(δ) denotes the Johnson radius for minimum distance δ. This shows that RM(2,m) codes are list-decodable up to radius η for any constant η < 1/2 in time polynomial in the block-length. Over small fields Fq, we present list-decoding algorithms in both the global and local settings that work up to the list-decoding radius. We conjecture that the list-decoding radius approaches the minimum distance (like over F), and prove this holds true when the degree is divisible by q-1.}, added-at = {2009-10-08T03:04:51.000+0200}, author = {Gopalan, Parikshit and Klivans, Adam R. and Zuckerman, David}, bibsource = {DBLP, http://dblp.uni-trier.de}, biburl = {https://www.bibsonomy.org/bibtex/23f328a22346623db260c513bf94b0df2/ytyoun}, booktitle = {STOC}, crossref = {DBLP:conf/stoc/2008}, doi = {10.1145/1374376.1374417}, editor = {Ladner, Richard E. and Dwork, Cynthia}, interhash = {b308ef323e3164af7ed36c4f9c74e4f9}, intrahash = {3f328a22346623db260c513bf94b0df2}, isbn = {978-1-60558-047-0}, keywords = {codes error-correcting-codes list_decoding reed-muller}, pages = {265-274}, publisher = {ACM}, timestamp = {2016-06-14T14:21:11.000+0200}, title = {List-decoding reed-muller codes over small fields}, year = 2008 }