Deterministic Approximation Algorithms for the Nearest Codeword Problem

DOI10.1007/978-3-642-03685-9_26zbMath1255.68298OpenAlexW1518498106MaRDI QIDQ3638889

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

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

Related Items (9)

Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN ⋮ Kolmogorov width of discrete linear spaces: an approach to matrix rigidity ⋮ On rigid matrices and \(U\)-polynomials ⋮ Learning parities in the mistake-bound model ⋮ The Distributions of Functions Related to Parametric Integer Optimization ⋮ On matrix rigidity and locally self-correctable codes ⋮ Sparse Solutions of Linear Diophantine Equations ⋮ Improved learning of \(k\)-parities ⋮ The remote set problem on lattices

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