Name
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 --r - ε) from R for any ε r,ε-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 η q, 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1374376.1374417 | STOC |
Keywords | Field | DocType |
larger radius,johnson radius,list-decoding radius,minimum distance,radius 2-r,small field,reed-muller code,deterministic list-decoder,local list-decoding algorithm,word r,relative distance 2-r,local setting,reed muller code,error rate,information theory,reed muller codes,list decoding | Discrete mathematics,Combinatorics,Oracle,Reed–Muller code,List decoding,Mathematics | Conference |
ISSN | Citations | PageRank |
0737-8017 | 29 | 1.29 |
References | Authors | |
25 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Parikshit Gopalan | 1 | 1186 | 61.52 |
| Adam R. Klivans | 2 | 946 | 51.75 |
| David Zucherman | 3 | 2588 | 266.65 |