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)

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
• The hardness of decoding linear codes with preprocessing
• Low rank approximation of binary matrices: column subset selection and generalizations
• Speeding up Graph Algorithms via Switching Classes
• On the hardnesses of several quantum decoding problems
• A Gale-Berlekamp permutation-switching problem
• Some applications of hypercontractive inequalities in quantum information theory
• 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)