### 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.