A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem

Details A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem

2010-10-07

arxiv.org/abs/1010.1481v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-509958