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

Per Austrin, Subhash Khot

Research output: Contribution to journalArticlepeer-review


We present a simple deterministic gap-preserving reduction from SAT to the minimum distance of code problem over F{double-struck}2. We also show how to extend the reduction to work over any fixed 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 nontrivial coding theoretic constructions, whereas our reduction is elementary. As an additional feature, our reduction gives hardness within a constant factor even for asymptotically good codes, i.e., having constant positive rate and relative distance. Previously, it was not known how to achieve a deterministic reduction for such codes.

Original languageEnglish (US)
Article number6868217
Pages (from-to)6636-6645
Number of pages10
JournalIEEE Transactions on Information Theory
Issue number10
StatePublished - Oct 1 2014


  • Linear code
  • computational complexity

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'A simple deterministic reduction for the gap minimum distance of code problem'. Together they form a unique fingerprint.

Cite this