On the Hardness of Decoding the Gale–Berlekamp Code

DOI10.1109/TIT.2007.915716MaRDI QIDQ3604688zbMATH OpenFDO

Authors Ron M. Roth, Krishnamurthy Viswanathan

Publication date 24 February 2009

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/TIT.2007.915716

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decoding (94B35)

Recommendations

• Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
• The hardness of decoding linear codes with preprocessing
• Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
• Hard Problems of Algebraic Geometry Codes
• The intractability of computing the minimum distance of a code

Cited in

(8)

• Patience of matrix games
• On the hardnesses of several quantum decoding problems
• Some applications of hypercontractive inequalities in quantum information theory
• Speeding up Graph Algorithms via Switching Classes
• The hardness of decoding linear codes with preprocessing
• A Gale-Berlekamp permutation-switching problem
• Low rank approximation of binary matrices: column subset selection and generalizations
• First order deformations of the Fourier matrix

This page was built for publication: On the Hardness of Decoding the Gale–Berlekamp Code

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