------- METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011) ------- Workshop on Metric embeddings, algorithms and hardness of approximation January 17-21, 2011 ------- Jan 20, 9:00-10:00 Per Austrin (U. Toronto) Approximability of Minimum Distance of Codes ------- The focus of this talk is the problem of computing the minimum distance of a linear code. This problem is NP-hard, and we give an overview of what is known about the approximability of this problem. We also describe a new, elementary proof of NP-hardness of approximation for the problem (joint work with Subhash Khot).
