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: Miklós Ajtai, The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.10-19, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276705]
• 2: Sanjeev Arora , László Babai , Jacques Stern , Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, Journal of Computer and System Sciences, v.54 n.2, p.317-331, April 1997 [doi>10.1006/jcss.1997.1472]
• 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: Jin-Yi Cai , Ajay Nerurkar, Approximating the SVP to within a factor (1+1/dimE) is NP-Hard under randomized reductions, Journal of Computer and System Sciences, v.59 n.2, p.221-239, Oct. 1999 [doi>10.1006/jcss.1999.1649]
• 5: Qi Cheng , Daqing Wan, On the List and Bounded Distance Decodability of Reed-Solomon Codes, SIAM Journal on Computing, v.37 n.1, p.195-209, April 2007 [doi>10.1137/S0097539705447335]
• 6: Qi Cheng , Daqing Wan, Complexity of Decoding Positive-Rate Reed-Solomon Codes, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_24]
• 7: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 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 , Oded Regev, Tensor-based hardness of the shortest vector problem to within almost polynomial factors, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250859]
• 10: Subhash Khot, Hardness of approximating the shortest vector problem in lattices, Journal of the ACM (JACM), v.52 n.5, p.789-808, September 2005 [doi>10.1145/1089023.1089027]
• 11: Daniele Micciancio, The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant, SIAM Journal on Computing, v.30 n.6, p.2008-2035, 2001 [doi>10.1137/S0097539700373039]
• 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, v.66 n.219, p.1195-1212, July 1997 [doi>10.1090/S0025-5718-97-00835-1]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Theory

Keywords:
NP-complete, approximation algorithm, coding theory, minimum distance problem