A Deterministic Reduction for the Gap Minimum Distance Problem

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 the NP-complete in [14]. In [8], 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 2(log1-epsilon n) unless NP subset of RTIME(2(polylog(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 tome to the factor 2(log1-epsilon) n unless NP subset of DTIME (2(polylog(n))). As the main technical contribution, for any constant 2/3 < rho < 1, we present a deterministic algorithm that give 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 rho d(C) such that a projection at some s coordinates sends the codewords in the ball subjectively 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.