Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0001-8217-0158
2014 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 60, no 10, 6636-6645 p.Article in journal (Refereed) Published
Abstract [en]

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 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.

Place, publisher, year, edition, pages
2014. Vol. 60, no 10, 6636-6645 p.
Keyword [en]
Linear code, computational complexity
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-154750DOI: 10.1109/TIT.2014.2340869ISI: 000342416900048Scopus ID: 2-s2.0-84907221430OAI: oai:DiVA.org:kth-154750DiVA: diva2:761072
Note

QC 20141105

Available from: 2014-11-05 Created: 2014-10-27 Last updated: 2017-12-05Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Austrin, Per

Search in DiVA

By author/editor
Austrin, Per
By organisation
Theoretical Computer Science, TCS
In the same journal
IEEE Transactions on Information Theory
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 95 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf