NP-Hardness of Reed-solomon Decoding and the Prouhet-Tarry-Escott Problem скачать в хорошем качестве

NP-Hardness of Reed-solomon Decoding and the Prouhet-Tarry-Escott Problem

Elena Grigorescu speaks at the Workshop on Additive Combinatorics held at the Center of Mathematical Sciences and Applications in October, 2017. Abstract: I will discuss the complexity of decoding Reed-Solomon codes, and some results establishing NP-hardness for asymptotically smaller decoding radii than the maximum likelihood decoding radius. These results follow from the study of a generalization of the classical Subset Sum problem to higher moments, which may be of independent interest. I will further discuss a connection with the Prouhet-Tarry-Escott problem studied in Number Theory, which turns out to capture a main barrier in extending our techniques to smaller radii. Joint work with Venkata Gandikota and Badih Ghazi.