A deterministic reduction for the gap minimum distance problem: [extended abstract]

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 [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-ε n} unless NP ⊆ 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 time to the factor 2^log1-εn unless NP ⊆ DTIME(2^polylog(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 a projection at some 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.

References

1. Miklos Ajtai. The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In Proc. 30th ACM Symp. on Theory of Computing, pages 10--19, 1998.
2. Sanjeev Arora, Laszlo Babai, Jacques Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes and systems of linear equations. Journal of Computer and System Sciences, 54:317--331, 1997.
3. Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. van Tilborg. On the inherent intractability of certain coding problems. IEEE Transactions of Information Theory, 24(3):384--386, 1978.
4. J.-Y. Cai and A. Nerurkar. Approximating the svp to within a factor (1 1/dim^ε) is NP-hard under randomized reductions. J. of Comput. Syst. Sci., 59(2):221--239, 1999.
5. Qi Cheng and Daqing Wan. On the list and bounded distance decodability of Reed-Solomon codes. SIAM Journal on Computing, 37(1):195--209, 2007. Special Issue on FOCS 2004.
6. Qi Cheng and Daqing Wan. Complexity of decoding positive-rate Reed-Solomon codes. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), volume 5125 of Lecture Notes in Computer Science. Springer-Verlag, 2008.
7. Stephen Cook. The complexity of theorem proving procedures. In Proc. 3rd ACM Symp. on Theory of Computing, pages 151--158, 1971.
8. Ilya Dumer, Daniele Micciancio, and Madhu Sudan. Hardness of approximating the minimum distance of a linear code. IEEE Transactions on Information Theory, 49(1):22--37, 2003.
9. Ishay Haviv and Oded Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In Proc. 39th ACM Symp. on Theory of Computing, pages 469--477, 2007.
10. Subhash Khot. Hardness of approximating the shortest vector problem in lattices. Journal of ACM, 52(5):789--808, 2005.
11. D. Micciancio. The shortest vector problem is NP-hard to approximate to within some constant. SIAM J. on Computing, 30(6):2008--2035, 2001.
12. Victor Shoup. New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54:435--447, 1990.
13. P. van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical report, Mathematische INstituut, University of Amsterdam, 1981.
14. Alexander Vardy. The intractability of computing the minimum distance of a code. IEEE Trans. Inform. Theory, 43(6):1757--1766, 1997.
15. Daqing Wan. Generators and irreducible polynomials over finite fields. Mathematics of Computation, 66(219):1195--1212, 1997.

Index Terms

• Theory of computation

  • Design and analysis of algorithms