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.