Universal Hardness From Masking ChannelsResearch Paper
Given a class of predictors (Boolean circuits of bounded size, models of a fixed architecture), why is a labeling hard to approximate by members of ? The hardcore lemma of complexity theory answers this for Boolean labels and the 0-1 loss: if every errs on a -fraction of inputs, then there is a measure of…