The hardness of decoding linear codes with preprocessing

DOI10.1109/18.52484zbMATH Open0704.94022OpenAlexW2171712712MaRDI QIDQ3484767FDOQ3484767

Authors: Jehoshua Bruck, Moni Naor 

Publication date: 1990

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

Full work available at URL: https://resolver.caltech.edu/CaltechAUTHORS:BRUieeetit90b

Recommendations

• Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
• Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
• scientific article; zbMATH DE number 1284420
• The complexity of information set decoding
• On the Hardness of Decoding the Gale–Berlekamp Code

zbMATH Keywords

complexity theorypolynomial time algorithmmaximum likelihood decoding of linear block codes

Mathematics Subject Classification ID

Decoding (94B35)

Cited In (27)

• Computing coset leaders and leader codewords of binary codes
• Minimal linear codes constructed from partial spreads
• On the Hardness of Decoding the Gale–Berlekamp Code
• Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN
• Minimal linear codes constructed from functions
• Hardness of approximating the closest vector problem with pre-processing
• A commutative algebra approach to linear codes
• Minimal linear codes arising from blocking sets
• On a Gröbner bases structure associated to linear codes
• On the hardnesses of several quantum decoding problems
• Maximal intersection queries in randomized input models
• On the ideal associated to a linear code
• Minimal codewords arising from the incidence of points and hyperplanes in projective spaces
• The inapproximability of lattice and coding problems with preprocessing
• Decoding of Reed Solomon codes beyond the error-correction bound
• Minimal linear codes constructed from hierarchical posets with two levels
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• An inductive construction of minimal codes
• On the equivalence of two post-quantum cryptographic families
• Fault-detection in networks
• An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm
• Weighted counting of solutions to sparse systems of equations
• Designing quantum circuits for decoding binary linear codes
• Decomposition of modular codes for computing test sets and Graver basis
• On the weight distribution of some minimal codes
• The hardness of solving subset sum with preprocessing
• Bounded distance decoding of linear error-correcting codes with Gröbner bases

This page was built for publication: The hardness of decoding linear codes with preprocessing

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