hi,
ELEGANT idea I must say. the idea of being able to look at the m class in a m-fold prediction task as an error correcting code is frankly just too cool for me. The only problem is the paper says nothing about the difficulty of the problems constructed now and just mentions in passing that high values of rho would imply more difficult problems.

As error correcting codes are usually designed taking in to consideration the kind of errors that the underlying channel introduces, it would be interesting to look at the design of codes for multi-class learning problem by analysing the error characteristics of a given base algorithm over the simple encoding first.. meaning.

assume that the columns are binary representations of 0, 1,2 ..m-1
and then see if there are any particular kind of errors are prevalent, and then use that criterion to come up with a better code.

also certain codes (whatever be the minimum distance) could makes the transformed problem harder.

sameer