Deterministic Approximation Algorithms for the Nearest Codeword Problem

DOI10.1007/978-3-642-03685-9_26MaRDI QIDQ3638889zbMATH OpenOpenAlexFDO

Authors Noga Alon, Rina Panigrahy, Sergey Yekhanin

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2010/2413/

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Linear codes (general theory) (94B05)

Recommendations

• Hardness of approximating the minimum distance of a linear code
• A deterministic reduction for the gap minimum distance problem (extended abstract)
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• More on average case vs approximation complexity
• The intractability of computing the minimum distance of a code

Cited in

(18)

• Learning parities in the mistake-bound model
• Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN
• The remote set problem on lattices
• Kolmogorov width of discrete linear spaces: an approach to matrix rigidity
• Hardness of approximating the minimum distance of a linear code
• The distributions of functions related to parametric integer optimization
• A deterministic reduction for the gap minimum distance problem (extended abstract)
• Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
• Sparse Solutions of Linear Diophantine Equations
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
• Improved learning of \(k\)-parities
• On matrix rigidity and locally self-correctable codes
• New Results on the Remote Set Problem and Its Applications in Complexity Study
• Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
• Improved lower bounds for approximating parameterized nearest codeword and related problems under ETH
• Total functions in the polynomial hierarchy
• On rigid matrices and \(U\)-polynomials

This page was built for publication: Deterministic Approximation Algorithms for the Nearest Codeword Problem

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