DIMACS Theoretical Computer Science Seminar


Title: A Deterministic Reduction for the Gap Minimum Distance Problem

Speaker: Qi Cheng, University of Oklahoma

Date: Wednesday, April 8, 2009 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


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. The gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction. In this talk, we present a deterministic reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless P=NP. This is a joint work with Daqing Wan at UC Irvine.