A simple deterministic reduction for the gap minimum distance of code problem

DOI10.1007/978-3-642-22006-7_40MaRDI QIDQ5892608zbMATH OpenOpenAlexFDO

Authors Per Austrin, Subhash Khot

Publication date 6 July 2011

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.1481

Mathematics Subject Classification ID

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

Abstract: We present a simple deterministic gap-preserving reduction from SAT to the Minimum Distance of Code Problem over $F_2$. We also show how to extend the reduction to work over any finite field. Previously a randomized reduction was known due to Dumer, Micciancio, and Sudan, which was recently derandomized by Cheng and Wan. These reductions rely on highly non-trivial coding theoretic constructions whereas our reduction is elementary. As an additional feature, our reduction gives a constant factor hardness even for asymptotically good codes, i.e., having constant rate and relative distance. Previously it was not known how to achieve deterministic reductions for such codes.

Recommendations

• A deterministic reduction for the gap minimum distance problem (extended abstract)
• Hardness of approximating the minimum distance of a linear code
• The intractability of computing the minimum distance of a code
• scientific article; zbMATH DE number 7250164
• Hard Problems of Algebraic Geometry Codes

Cites work

• A deterministic reduction for the gap minimum distance problem (extended abstract)
• A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
• Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
• Complexity of Decoding Positive-Rate Reed-Solomon Codes
• Hardness of approximating the minimum distance of a linear code
• scientific article; zbMATH DE number 5485482 (Why is no real title available?)
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• Interactive proofs and the hardness of approximating cliques
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Pseudorandom bits for polynomials
• The intractability of computing the minimum distance of a code
• The shortest vector in a lattice is hard to approximate to within some constant
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Unconditional pseudorandom generators for low degree polynomials

Cited in

(5)

• A Deterministic Reduction for the Gap Minimum Distance Problem
• Minimum distance computation of linear codes via genetic algorithms with permutation encoding
• scientific article; zbMATH DE number 7250164 (Why is no real title available?)
• A deterministic reduction for the gap minimum distance problem (extended abstract)
• A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem

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

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