The hardness of decoding linear codes with preprocessing

DOI10.1109/18.52484MaRDI QIDQ3484767zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

complexity theorypolynomial time algorithmmaximum likelihood decoding of linear block codes

Mathematics Subject Classification ID

Decoding (94B35)

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

Cited in

(29)

• Bounded distance decoding of linear error-correcting codes with Gröbner bases
• 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
• Hardness of approximating the closest vector problem with pre-processing
• Minimal linear codes constructed from functions
• 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
• On the ideal associated to a linear code
• Maximal intersection queries in randomized input models
• Minimal codewords arising from the incidence of points and hyperplanes in projective spaces
• On the maximum-likelihood decoding problem
• Decoding of Reed Solomon codes beyond the error-correction bound
• The inapproximability of lattice and coding problems with preprocessing
• 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
• Fault-detection in networks
• On the equivalence of two post-quantum cryptographic families
• 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
• Decomposition of modular codes for computing test sets and Graver basis
• Designing quantum circuits for decoding binary linear codes
• Characterizations for minimal codes: graph theory approach and algebraic approach over finite chain rings
• On the weight distribution of some minimal codes
• The hardness of solving subset sum with preprocessing

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)