NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem

DOI10.1137/16M110349XMaRDI QIDQ4581908zbMATH OpenOpenAlexWikidataFDO

Authors Venkata Gandikota, Badih Ghazi, Elena Grigorescu

Publication date 21 August 2018

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.03069

zbMATH Keywords

Prouhet-Tarry-Escott problempolynomial reconstructionbounded distance decodingReed-Solomon decdoing

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: 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 Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when it is efficiently solvable (i.e., the Johnson radius). We show the first NP-hardness results for asymptotically smaller decoding radii than the maximum likelihood decoding radius of Guruswami and Vardy. Specifically, for Reed-Solomon codes of length $N$ and dimension $K=O(N)$, we show that it is NP-hard to decode more than $N-K-cfraclogNloglogN$ errors (with $c>0$ an absolute constant). Moreover, we show that the problem is NP-hard under quasipolynomial-time reductions for an error amount $>N-K-clogN$ (with $c>0$ an absolute constant). These results follow from the NP-hardness of a generalization of the classical Subset Sum problem to higher moments, called {em Moments Subset Sum}, which has been a known open problem, and which may be of independent interest. We further reveal a strong connection with the well-studied Prouhet-Tarry-Escott problem in Number Theory, which turns out to capture a main barrier in extending our techniques. We believe the Prouhet-Tarry-Escott problem deserves further study in the theoretical computer science community.

Recommendations

• Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
• Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
• Complexity of Decoding Positive-Rate Reed-Solomon Codes
• On the List and Bounded Distance Decodability of Reed–Solomon Codes
• Hard Problems of Algebraic Geometry Codes

Cites work

• scientific article; zbMATH DE number 3158050 (Why is no real title available?)
• scientific article; zbMATH DE number 5296403 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3758416 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 607286 (Why is no real title available?)
• scientific article; zbMATH DE number 1559526 (Why is no real title available?)
• scientific article; zbMATH DE number 3055095 (Why is no real title available?)
• A computational introduction to number theory and algebra
• Algebraic soft-decision decoding of reed-solomon codes
• Approximating CVP to within almost-polynomial factors is NP-hard
• Complexity of Decoding Positive-Rate Primitive Reed–Solomon Codes
• Computational investigations of the Prouhet-Tarry-Escott Problem
• Decoding of Reed Solomon codes beyond the error-correction bound
• Encoding and error-correction procedures for the Bose-Chaudhuri codes
• Every list-decodable code for high noise has abundant near-optimal rate puncturings
• Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
• Hard Problems of Algebraic Geometry Codes
• Hardness of Reconstructing Multivariate Polynomials over Finite Fields
• Hardness of approximating the minimum distance of a linear code
• Improved Inapproximability of Lattice and Coding Problems With Preprocessing
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Learning polynomials with queries: The highly noisy case
• Local list-decoding and testing of random linear codes from high error
• Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
• On Vinogradov's mean value theorem
• On the List and Bounded Distance Decodability of Reed–Solomon Codes
• On the subset sum problem over finite fields
• Polynomial Codes Over Certain Finite Fields
• Prouhet's 1851 Solution of the Tarry-Escott Problem of 1910
• Some optimal inapproximability results
• The Prouhet-Tarry-Escott problem revisited
• The complexity of satisfiability problems
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• The inapproximability of lattice and coding problems with preprocessing

Cited in

(6)

• Moment subset sums over finite fields
• Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
• Complexity of Decoding Positive-Rate Reed-Solomon Codes
• Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
• An improvement of Prouhet's 1851 result on multigrade chains
• Complexity of Decoding Positive-Rate Primitive Reed–Solomon Codes

This page was built for publication: NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581908)