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

DOI10.1137/16M110349XzbMATH Open1444.94131arXiv1611.03069OpenAlexW2887573924WikidataQ129476643 ScholiaQ129476643MaRDI QIDQ4581908FDOQ4581908

Elena Grigorescu, Badih Ghazi, Venkata Gandikota

Publication date: 21 August 2018

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

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.

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)

Cites Work

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

Cited In (5)

• 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
• Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
• Moment subset sums over finite fields

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)