Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
Chong Shangguan, Itzhak Tamo
Abstract
List-decoding of Reed-Solomon (RS) codes beyond the so called Johnson radius has been one of the main open questions in coding theory and theoretical computer science since the work of Guruswami and Sudan. It is now known by the work of Rudra and Wootters, using techniques from high dimensional probability, that over large enough alphabets there exist RS codes that are indeed list-decodable beyond this radius.
Topics & Concepts
Reed–Solomon error correctionList decodingDecoding methodsCoding theoryReed–Muller codeRADIUSComputer scienceCoding (social sciences)Discrete mathematicsMathematicsTheoretical computer scienceBlock codeConcatenated error correction codeAlgorithmStatisticsComputer networkCoding theory and cryptographygraph theory and CDMA systemsCellular Automata and Applications