2 papers
cs.IT2016
NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem
Venkata Gandikota, Badih Ghazi, Elena Grigorescu
Establishing the complexity of {\em Bounded Distance Decoding} for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE…
cs.IT2013
Linear Programming Decoding of Spatially Coupled Codes
Louay Bazzi, Badih Ghazi, Rudiger Urbanke
For a given family of spatially coupled codes, we prove that the LP threshold on the BSC of the graph cover ensemble is the same as the LP threshold on the BSC of the derived spati…