[Metric 2011] Per Austrin

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