Some tasks are hard: every model in a chosen family makes many mistakes. A classic result, the hardcore lemma, says such tasks hide a subset of inputs where models do no better than random guessing. The authors generalize this using masking channels, rules that add input-dependent noise to labels.
They prove hardness equals the least noise a masking channel must add before labels look like pure random noise. This best fidelity is necessary and sufficient, and works for non-Boolean labels and broad families of error measures.
This turns hardness into a precise, measurable quantity and gives a universal channel certifying hardness for many error measures at once, allowing proofs that no model in a class can beat chance before costly training.