On the Hardness of Decoding the Gale–Berlekamp Code

DOI10.1109/TIT.2007.915716zbMATH Open1311.94121MaRDI QIDQ3604688FDOQ3604688

Authors: Ron M. Roth, Krishnamurthy Viswanathan 

Publication date: 24 February 2009

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

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

Mathematics Subject Classification ID

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

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)