Error-Correcting Tournaments

We present a family of pairwise tournaments reducing \(k\)-class classification to binary classification. These reductions are provably robust against a constant fraction of binary errors. The results improve on the PECOC construction \cite{SECOC} with an exponential improvement in computation, from \(O(k)\) to \(O({log}_2k)\), and the removal of a square root in the regret dependence, matching the best possible computation and regret up to a constant.