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

Per Austrin, Subhash Khot

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a simple deterministic gap-preserving reduction from SAT to the Minimum Distance of Code Problem over . We also show how to extend the reduction to work over any finite field (of constant size). Previously a randomized reduction was known due to Dumer, Micciancio, and Sudan [9], which was recently derandomized by Cheng and Wan [7, 8]. 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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
Pages474-485
Number of pages12
EditionPART 1
DOIs
StatePublished - 2011
Event38th International Colloquium on Automata, Languages and Programming, ICALP 2011 - Zurich, Switzerland
Duration: Jul 4 2011Jul 8 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6755 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other38th International Colloquium on Automata, Languages and Programming, ICALP 2011
CountrySwitzerland
CityZurich
Period7/4/117/8/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint 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