1A Deterministic Reduction for the Gap Minimum Distance Problem

Abstract—Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete in [15]. In [9], the gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction. It was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2log 1− n unless NP ⊆ RTIME(2polylog(n)). In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless P = NP. We also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2log 1− n unless NP ⊆ DTIME(2polylog(n)). As the main technical contribution, for any constant 2/3 < ρ < 1, we present a deterministic algorithm that given a positive integer s, runs in time poly(s) and constructs a code C of length poly(s) with an explicit Hamming ball of radius ρd(C), such that the projection at the first s coordinates sends the codewords in the ball surjectively onto a linear subspace of dimension s, where d(C) denotes the minimum distance of C. The codes are obtained by concatenating Reed-Solomon codes with Hadamard codes. Index Terms—Coding theory, NP-complete, approximation algorithm, minimum distance problem