Name
Abstract | ||
|---|---|---|
Lifted Reed–Solomon codes are a natural affine-invariant family of error-correcting codes, which generalize Reed–Muller codes. They were known to have efficient local-testing and local-decoding algorithms (comparable with the known algorithms for Reed–Muller codes), but with significantly better rate. We give efficient algorithms for list decoding and local list decoding of lifted codes. Our algorithms are based on a new technical lemma, which says that the codewords of lifted codes are low degree polynomials when viewed as univariate polynomials over a big field (even though they may be very high degree when viewed as multivariate polynomials over a small field). |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/TIT.2016.2538766 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
Decoding,Frequency modulation,Interpolation,Reed-Solomon codes,Complexity theory,Encoding | Discrete mathematics,Combinatorics,Sequential decoding,Berlekamp–Welch algorithm,Computer science,Block code,Expander code,Algorithm,Linear code,Reed–Muller code,Tornado code,List decoding | Journal |
Volume | Issue | ISSN |
abs/1412.0305 | 5 | 0018-9448 |
Citations | PageRank | References |
4 | 0.47 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alan Guo | 1 | 4 | 0.47 |
| Swastik Kopparty | 2 | 384 | 32.89 |