A deterministic reduction for the gap minimum distance problem

DOI10.1145/1536414.1536421zbMath1304.94111OpenAlexW1997003296MaRDI QIDQ5172695

Daqing Wan, Qi Cheng

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536421

zbMATH Keywords

approximation algorithmNP-completecoding theoryminimum distance problem

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 (4)

Bi-Covering: Covering Edges with Two Small Subsets of Vertices ⋮ A new sieve for distinct coordinate counting ⋮ A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem ⋮ On succinct arguments and witness encryption from groups

This page was built for publication: A deterministic reduction for the gap minimum distance problem